Abstract
Mim-width and sim-width are among the most powerful graph width parameters, with sim-width more powerful than mim-width, which is in turn more powerful than clique-width. While several
NP
-hard graph problems become tractable for graph classes whose mim-width is bounded and quickly computable, no algorithmic applications of boundedness of sim-width are known. In [Kang et al., A width parameter useful for chordal and co-comparability graphs, Theoretical Computer Science, 704:1-17, 2017], it is asked whether Independent Set and 3-Colouring are
NP
-complete on graphs of sim-width at most 1. We observe that, for each
k
∈
N
, List
k
-Colouring is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. Moreover, we show that if the same holds for Independent Set, then Independent
H
-Packing is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. This problem is a common generalisation of Independent Set, Induced Matching, Dissociation Set and k
-Separator.
We also make progress toward classifying the mim-width of
(
H
1
,
H
2
)
-free graphs in the case
H
1
is complete or edgeless. Our results solve some open problems in [Brettell et al., Bounding the mim-width of hereditary graph classes, Journal of Graph Theory, 99(1):117-151, 2022].
Original language | English |
---|---|
Article number | 113825 |
Number of pages | 20 |
Journal | Theoretical Computer Science |
Volume | 955 |
Early online date | 20 Mar 2023 |
DOIs | |
Publication status | Published - 26 Apr 2023 |
Fingerprint
Dive into the research topics of 'On algorithmic applications of sim-width and mim-width of (H 1,H 2)-free graphs'. Together they form a unique fingerprint.Student theses
-
Graph width parameters: from structure to algorithm
Yang, S. (Author), Munaro, A. (Supervisor), Barnes, D. (Supervisor) & Lin, Y.-F. (Supervisor), Dec 2024Student thesis: Doctoral Thesis › Doctor of Philosophy
File