Synapse
⌘+K
Synapse
PulseExploreClubsResearchersJournals
Instagram
HomeClubsExplore
October 2, 2025ACM Transactions on Computational LogicOpen Access

Computing and Certifying Twin-Width Using Logic

View Full Paper
Ask AI
Bookmark
Share

Authors

ASAndré SchidlerSSStefan Szeider

Discussion

Loading...

Member takes

Overview

This research demonstrates exact twin-width computation using SAT encodings and Branch & Bound, highlighting algorithmic strategies for efficiency.

Key Points

  • Efficiently computes twin-width, aiding NP-hard problem solutions in graphs with bounded twin-width.
  • Introduces SAT encodings that enhance performance and explores formulations of twin-width in various instances.
  • Implements a Branch & Bound approach that improves efficiency by utilizing cached partial solutions for larger graphs.
  • Develops a verification framework that provides verifiable proofs for computed twin-width, contributing to theoretical graph insights.

Cite This Study

Schidler et al. (2025) studied this question.

synapsesocial.com/papers/68de6f3a83cbc991d0a22841https://doi.org/10.1145/3769869
View Full Paper
Ask AI
Bookmark
Share

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

  1. 1Twin-width IV: ordered graphs and matrices2024 · 6 citations
  2. 2Twin-width and permutations2024 · 3 citations
  3. 3First-Order Logic and Twin-Width for Some Geometric Graphs2026
  4. 4Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings2025
  5. 5Graph Theory2025