Deciding twin-width at most 4 is NP-complete
| Autor: | Bergé, Pierre, Bonnet, Édouard, Déprés, Hugues |
|---|---|
| Přispěvatelé: | Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019) |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Computational Complexity (cs.CC) 68Q17 Computer Science - Computational Complexity lower bounds Theory of computation → Fixed parameter tractability Theory of computation → Graph algorithms analysis Computer Science - Data Structures and Algorithms FOS: Mathematics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] Combinatorics (math.CO) F.2.2 Computer Science - Discrete Mathematics Twin-width |
| Zdroj: | 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022) 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2022), Jul 2022, Paris, France. ⟨10.4230/LIPIcs.ICALP.2022.18⟩ |
| DOI: | 10.4230/LIPIcs.ICALP.2022.18⟩ |
| Popis: | We show that determining if an $n$-vertex graph has twin-width at most 4 is NP-complete, and requires time $2^{\Omega(n/\log n)}$ unless the Exponential-Time Hypothesis fails. Along the way, we give an elementary proof that $n$-vertex graphs subdivided at least $2 \log n$ times have twin-width at most 4. We also show how to encode trigraphs $H$ (2-edge colored graphs involved in the definition of twin-width) into graphs $G$, in the sense that every $d$-sequence (sequence of vertex contractions witnessing that the twin-width is at most $d$) of $G$ inevitably creates $H$ as an induced subtrigraph, whereas there exists a partial $d$-sequence that actually goes from $G$ to $H$. We believe that these facts and their proofs can be of independent interest. Comment: 30 pages, 17 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|