Bounding the mim‐width of hereditary graph classes

DOI10.1002/JGT.22730MaRDI QIDQ6056798zbMATH OpenOpenAlexFDO

Authors Nick Brettell, Jake Horsfield, Andrea Munaro, Giacomo Paesani, Daniël Paulusma

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.05018

zbMATH Keywords

clique-widthhereditary graph classmim-widthwidth parameter

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A large number of NP-hard graph problems become polynomial-time solvable on graph classes where the mim-width is bounded and quickly computable. Hence, when solving such problems on special graph classes, it is helpful to know whether the graph class under consideration has bounded mim-width. We first extend the toolkit for proving (un)boundedness of mim-width of graph classes. This enables us to initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes. For a given graph $H$, the class of $H$-free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for $(H_1,H_2)$-free graphs. We find several general classes of $(H_1,H_2)$-free graphs having unbounded clique-width, but the mim-width is bounded and quickly computable. We also prove a number of new results showing that, for certain $H_1$ and $H_2$, the class of $(H_1,H_2)$-free graphs has unbounded mim-width. Combining these with known results, we present summary theorems of the current state of the art for the boundedness of mim-width for $(H_1,H_2)$-free graphs.

Recommendations

• Bounding the Mim-Width of Hereditary Graph Classes.
• Lower bounds on the mim-width of some graph classes
• scientific article; zbMATH DE number 1979486
• On the size of hereditary classes of graphs
• Clique-width for hereditary graph classes
• A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
• Linear clique-width for hereditary classes of cographs
• On the structure of hereditary classes of graphs
• Uncountably many minimal hereditary classes of graphs of unbounded clique-width
• scientific article; zbMATH DE number 468640

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Approximating clique-width and branch-width
• Boolean-width of graphs
• Bounding clique-width via perfect graphs
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Clique-width and well-quasi-ordering of triangle-free graph classes
• Clique-width for graph classes closed under complementation
• Clique-width for hereditary graph classes
• Clique-width of graphs defined by one-vertex extensions
• Colouring diamond-free graphs
• Colouring vertices of triangle-free graphs without forests
• Edge dominating set and colorings on graphs with fixed clique-width
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
• Graph classes with structured neighborhoods and algorithmic applications
• Graph minors. X: Obstructions to tree-decomposition
• Hardness of computing width parameters based on branch decompositions over the vertex set
• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• scientific article; zbMATH DE number 7651174 (Why is no real title available?)
• List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
• List k-colouring P_t-free graphs: a mim-width perspective
• List coloring in the absence of a linear forest
• Lower bounds on the mim-width of some graph classes
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Mim-width. I. Induced path problems
• Mim-width. II. The feedback vertex set problem
• Mim-width. III. Graph powers and generalized distance domination problems
• More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
• Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the induced matching problem
• On the tractability of optimization problems on \(H\)-graphs
• Recent developments on graphs of bounded clique-width
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Solving problems on generalized convex graphs via mim-width
• The behavior of clique-width under graph operations and graph transformations
• The Complexity of Coloring Circular Arcs and Chords
• Tight bounds on maximal and maximum matchings
• Understanding model counting for -acyclic CNF-formulas
• Upper bounds to the clique width of graphs

Cited in

(23)

• Mim-width. I. Induced path problems
• Mim-width. II. The feedback vertex set problem
• Mim-width. III. Graph powers and generalized distance domination problems
• Lower bounds on the mim-width of some graph classes
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Generalized distance domination problems and their complexity on graphs of bounded mim-width
• Tree pivot-minors and linear rank-width
• Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
• Computing subset transversals in \(H\)-free graphs
• Clique‐width: Harnessing the power of atoms
• Bounding the Mim-Width of Hereditary Graph Classes.
• Treewidth versus clique number. II: Tree-independence number
• Solving problems on generalized convex graphs via mim-width
• On \(d\)-stable locally checkable problems parameterized by mim-width
• New Width Parameters for Independent Set: One-Sided-Mim-Width and Neighbor-Depth
• Finding induced subgraphs from graphs with small mim-width
• On the hardness of generalized domination problems parameterized by mim-width
• Comparing width parameters on graph classes
• Computing subset vertex covers in H-free graphs
• Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
• Hamiltonicity parameterized by mim-width Is (indeed) para-NP-hard
• Sparse induced subgraphs in P₇-Free graphs of bounded clique number

This page was built for publication: Bounding the mim‐width of hereditary graph classes

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