-
Treewidth versus clique number : III. tree-independence number of graphs with a forbidden structureDallard, Clément Jean ; Milanič, Martin, 1980- ; Štorgel, KennyWe continue the study of (tw,ω)-bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding ... the extent to which this property has useful algorithmic implications for the Maximum Independent Set and related problems. In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. II. Tree-independence number, J. Comb. Theory, Ser. B, 164 (2024) 404–442], we introduced the tree-independence number, a min-max graph invariant related to tree decompositions. Bounded tree-independence number implies both (tw,ω)-boundedness and the existence of a polynomial-time algorithm for the Maximum Weight Independent Packing problem, provided that the input graph is given together with a tree decomposition with bounded independence number. In particular, this implies polynomial-time solvability of the Maximum Weight Independent Set problem. In this paper, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. The induced minor relation is of particular interest: we show that excluding either a K5 minus an edge or the 4-wheel implies the existence of a tree decomposition in which every bag is a clique plus at most 3 vertices, while excluding a complete bipartite graph K2,q implies the existence of a tree decomposition with independence number at most 2(q−1). These results are obtained using a variety of tools, including ℓ-refined tree decompositions, SPQR trees, and potential maximal cliques, and actually show that in the bounded cases identified in this work, one can also compute tree decompositions with bounded independence number efficiently. Applying the algorithmic framework provided by the previous paper in the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes, each of which properly contains the class of chordal graphs. In particular, these results apply to the class of 1-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019.Source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 167, jul. 2024, str. 338-391)Type of material - article, component part ; adult, seriousPublish date - 2024Language - englishCOBISS.SI-ID - 192775683
Author
Dallard, Clément Jean |
Milanič, Martin, 1980- |
Štorgel, Kenny
Topics
tree decomposition |
independence number |
tree-independence number |
induced minor |
SPQR tree |
minimal separator |
potential maximal clique |
drevesna dekompozicija |
neodvisnostno število |
drevesno neodvisnostno število |
induciran minor |
SPQR drevo |
minimalen separator |
potencialna maksimalna klika
source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 167, jul. 2024, str. 338-391)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Dallard, Clément Jean | 53750 |
Milanič, Martin, 1980- | 30211 |
Štorgel, Kenny | 53598 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.