Deciding twin-width at most 4 is NP-complete

DOI10.4230/LIPICS.ICALP.2022.18MaRDI QIDQ6560802zbMATH OpenFDO

Authors Pierre Bergé, Édouard Bonnet, Hugues Déprés

Publication date 24 June 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2022.18

zbMATH Keywords

lower boundstwin-width

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cited in

(23)

• Twin-width and transductions of proper \(k\)-mixed-thin graphs
• Planar graph with twin-width seven
• Twin-width of graphs with tree-structured decompositions
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Computing and certifying twin-width using logic
• Faster graph algorithms through DAG compression
• Computing twin-width parameterized by the feedback edge number
• On the twin-width of outerplanar graphs
• Computing twin-width parameterized by the feedback edge number and vertex integrity
• Twin-width of planar graphs is at most 8, and some related bounds
• PACE solver description: Touiouidth
• PACE solver description: exact (GUTHMI) and heuristic (GUTHM)
• PACE solver description: the PACE 2023 parameterized algorithms and computational experiments challenge: twinwidth
• Twin-width of graphs with tree-structured decompositions
• Stretch-width
• Fast convolutions for near-convex sequences
• Sparse graphs of twin-width 2 have bounded tree-width
• Twin-width of subdivisions of multigraphs
• Improved bounds for twin-width parameter variants with algorithmic applications to counting graph colorings
• Twin-width of graphs on surfaces
• Twin-width meets feedback edges and vertex integrity
• Twin-width one
• Twin-width. VIIIa: Delineation

This page was built for publication: Deciding twin-width at most 4 is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6560802)