Lower bounds on the mim-width of some graph classes

DOI10.1016/J.DAM.2017.04.043MaRDI QIDQ2413964zbMATH OpenOpenAlexFDO

Authors Stefan Mengel

Publication date 17 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

circle graphsco-comparability graphslower boundmim-widthstrongly chordal split graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: mim-width is a recent graph width measure that has seen applications in graph algorithms and problems related to propositional satisfiability. In this paper, we show linear lower bounds for the mim-width of strongly chordal split graphs, co-comparability graphs and circle graphs. This improves and refines lower bounds that were known before, some of them only conditionally. In the case of strongly chordal graphs not even a conditional lower bound was known before. All of the bounds given are optimal up to constants.

Recommendations

• Bounding the mim‐width of hereditary graph classes
• Mim-width. II. The feedback vertex set problem
• Mim-width. I. Induced path problems

Cites work

• Graph classes with structured neighborhoods and algorithmic applications
• HAMILTONian circuits in chordal bipartite graphs
• No small nondeterministic read-once branching programs for CNFs of bounded treewidth
• On compiling CNFs into structured deterministic DNNFs
• On satisfiability problems with a linear structure
• On tree width, bramble size, and expansion
• Solving #SAT and MAXSAT by Dynamic Programming
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The point-set embeddability problem for plane graphs
• Understanding model counting for -acyclic CNF-formulas

Cited in

(13)

• Well-partitioned chordal graphs
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Mim-width. III. Graph powers and generalized distance domination problems
• On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
• Bounding the mim‐width of hereditary graph classes
• Bounding the Mim-Width of Hereditary Graph Classes.
• Treewidth versus clique number. II: Tree-independence number
• Classes of intersection digraphs with good algorithmic properties
• Finding induced subgraphs from graphs with small mim-width
• Comparing width parameters on graph classes
• Lower bounds for leaf rank of leaf powers
• Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
• Hamiltonicity parameterized by mim-width Is (indeed) para-NP-hard

This page was built for publication: Lower bounds on the mim-width of some graph classes

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