-
Treewidth versus clique number : II. Tree-independence numberDallard, Clément Jean ; Milanič, Martin, 1980- ; Štorgel, KennyIn 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 (treewidth,omega)-bounded. The family of ... (treewidth,omega)-bounded graph classes provides a unifying framework for a variety of very different families of graph classes, including graph classes of bounded treewidth, graph classes of bounded independence number, intersection graphs of connected subgraphs of graphs with bounded treewidth, and graphs in which all minimal separators are of bounded size. While Chaplick and Zeman showed in 2017 that (treewidth,omega)-bounded graph classes enjoy some good algorithmic properties related to clique and coloring problems, it is an interesting open problem to which extent (treewidth,omega)-boundedness has useful algorithmic implications for problems related to independent sets. We provide a partial answer to this question by identifying a sufficient condition for (treewidth,omega)-bounded graph classes to admit a polynomial-time algorithm for the Maximum Weight Independent Packing problem and, as a consequence, for the weighted variants of the Independent Set and Induced Matching problems. Our approach is based on a new min-max graph parameter related to tree decompositions. We define the independence number of a tree decomposition T of a graph as the maximum independence number over all subgraphs of G induced by some bag of T. The tree-independence number of a graph G is then defined as the minimum independence number over all tree decompositions of G. Boundedness of the tree-independence number is a refinement of (treewidth,omega)-boundedness that is still general enough to hold for all the aforementioned families of graph classes. 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 are given in the third paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure].Source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 164, jan. 2024, str. 404-442)Type of material - article, component part ; adult, seriousPublish date - 2024Language - englishCOBISS.SI-ID - 172914691
Author
Dallard, Clément Jean |
Milanič, Martin, 1980- |
Štorgel, Kenny
Topics
tree decomposition |
independence number |
tree-independence number |
weighted independent set |
drevesna dekompozicija |
neodvisnostno število |
drevesno neodvisnostno število |
utežena neodvisna množica |
uteženo neodvisno pakiranje
![loading ... loading ...](themes/default/img/ajax-loading.gif)
source: Journal of combinatorial theory. Series B. - ISSN 0095-8956 (Vol. 164, jan. 2024, str. 404-442)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
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.