Treewidth versus clique number. II: Tree-independence number

DOI10.1016/J.JCTB.2023.10.006MaRDI QIDQ6144406zbMATH OpenOpenAlexFDO

Authors Clément Dallard, Martin Milanič, Kenny Štorgel

Publication date 29 January 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

independence numbertree decompositionweighted independent settree-independence numberweighted independent packing

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In 2020, we initiated a systematic study of graph classes in which the treewidth can only be large due to the presence of a large clique, which we call $(mathrmtw,omega)$-bounded. While $(mathrmtw,omega)$-bounded graph classes are known to enjoy some good algorithmic properties related to clique and coloring problems, it is an interesting open problem whether $(mathrmtw,omega)$-boundedness also has useful algorithmic implications for problems related to independent sets. We provide a partial answer to this question by means of a new min-max graph invariant related to tree decompositions. We define the independence number of a tree decomposition $mathcalT$ of a graph as the maximum independence number over all subgraphs of $G$ induced by some bag of $mathcalT$. The tree-independence number of a graph $G$ is then defined as the minimum independence number over all tree decompositions of $G$. Generalizing a result on chordal graphs due to Cameron and Hell from 2006, we show that if a graph is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Packing problem can be solved in polynomial time. Applications of our general algorithmic result to specific graph classes will be given in the third paper of the series [Dallard, Milaniv{c}, and v{S}torgel, Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure].

Recommendations

• Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
• Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
• Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs

Cites work

• scientific article; zbMATH DE number 3889566 (Why is no real title available?)
• scientific article; zbMATH DE number 4210186 (Why is no real title available?)
• scientific article; zbMATH DE number 1303600 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1796975 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 1420906 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• scientific article; zbMATH DE number 7788454 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A characterisation of rigid circuit graphs
• A partial k-arboretum of graphs with bounded treewidth
• A survey of \(\chi\)-boundedness
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Approximating clique-width and branch-width
• Boolean-width of graphs
• Bounding the mim‐width of hereditary graph classes
• Clique-width for hereditary graph classes
• Clustering and domination in perfect graphs
• Coloring and Maximum Weight Independent Set of Rectangles
• Combinatorial problems on \(H\)-graphs
• Connected tree-width
• Decomposition by clique separators
• Easy problems for tree-decomposable graphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Efficient graph representations
• Fast FPT-approximation of branchwidth
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Geometric algorithms and combinatorial optimization
• Graph Classes: A Survey
• Graph classes with structured neighborhoods and algorithmic applications
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. III. Planar tree-width
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Independent domination in chordal graphs
• Independent packings in structured graphs
• Induced matchings
• Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Linear time solvable optimization problems on graphs of bounded clique-width
• Lower bounds on the mim-width of some graph classes
• Maximum weight independent set for claw-free graphs in polynomial time
• Maximum weight induced matching in some subclasses of bipartite graphs
• Mim-width. III. Graph powers and generalized distance domination problems
• Minor-matching hypertree width
• Node-Deletion Problems on Bipartite Graphs
• On \(H\)-topological intersection graphs
• On \(H\)-topological intersection graphs
• On rigid circuit graphs
• On the Relationship Between Clique-Width and Treewidth
• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• On the tractability of optimization problems on \(H\)-graphs
• Parameterized algorithms
• Partitioning a graph into small pieces with applications to path transversal
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Precoloring extension. I: Interval graphs
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Reducibility among combinatorial problems
• Representations of chordal graphs as subtrees of a tree
• Robust algorithms for restricted domains
• Satgraphs and independent domination. I
• Structural parameterizations with modulator oblivion
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Substitution and \(\chi\)-boundedness
• The Complexity of Coloring Circular Arcs and Chords
• The Pathwidth and Treewidth of Cographs
• The k-separator problem: polyhedra, complexity and approximation results
• The complexity of dissociation set problems in graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The weighted independent domination problem is NP-complete for chordal graphs
• Tree-chromatic number
• Tree-decompositions with bags of small diameter
• Treewidth computations. II. Lower bounds
• Treewidth versus clique number in graph classes with a forbidden structure
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Twin-width II: small classes
• Twin-width. I: Tractable FO model checking
• Upper bounds to the clique width of graphs

Cited in

(4)

• Bisimplicial separators
• Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
• Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
• Polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graphs

This page was built for publication: Treewidth versus clique number. II: Tree-independence number

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