Deciding twin-width at most 4 is NP-complete

2021/12/16 by Bergé, Pierre, Bonnet, Édouard, Déprés, Hugues · 3 citations
#68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2112.08953

Abstract

We show that determining if an n-vertex graph has twin-width at most 4 is NP-complete, and requires time 2^{Ω(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.

Cited by

• Coloring Hardness on Low Twin-Width Graphs
• UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
• Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings

Related

• Twin-width of Planar Graphs is at most 8, and some Related Bounds
• Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
• On Ahn-Hendrey-Kim-Oum question for twin-width of graphs with 6 vertices
• Computation of twin-width of graphs
• Twin-width one