Page 245 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 245
ALGORITHMIC GRAPH THEORY (MS-54)
Beyond treewidth: the tree-independence number
Martin Milanicˇ, martin.milanic@upr.si
University of Primorska, Slovenia
Coauthors: Clément Dallard, Kenny Štorgel
We introduce a new graph invariant called tree-independence number. This is a common gener-
alization of treewidth and independence number, in the sense that bounded treewidth or bounded
independence number implies bounded tree-independence number. The tree-independence num-
ber of a graph G is defined as the smallest positive integer k such that G has a tree decomposition
whose bags induce subgraphs of G with independence number at most k. While for k = 1 we
obtain the well-known class of chordal graphs, we show that the problem of computing the
tree-independence number of a graph is NP-hard in general.
We consider six graph containment relations (the subgraph, topological minor, and minor
relations, as well as their induced variants) and for each of them completely characterize graph
classes of bounded tree-independence number defined by a single forbidden graph with respect
to the relation. In each of these bounded cases, a tree decomposition with small independence
number can be computed efficiently, which implies polynomial-time solvability of the Maxi-
mum Weight Independent Set (MWIS) problem. This in particular applies to an infinite family
of generalizations of the class of chordal graphs, for which a polynomial-time algorithm for the
MWIS problem was given by Frank in 1976.
Width parameters and graph classes: the case of mim-width
Andrea Munaro, a.munaro@qub.ac.uk
Queen’s University Belfast, United Kingdom
Coauthors: Flavia Bonomo-Braberman, Nick Brettell, Daniël Paulusma, Jake Horsfield,
Giacomo Paesani
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 prob-
lems on special graph classes, it is helpful to know whether the graph class under consideration
has bounded mim-width. We extend the toolkit for proving (un)boundedness of mim-width of
graph classes and initiate a systematic study into bounding mim-width from the perspective
of hereditary graph classes. We present summary theorems of the current state of the art for
the boundedness of mim-width for (H1, H2)-free graphs and observe several interesting conse-
quences. We also study the mim-width of generalized convex graphs. This allows us to re-prove
and strengthen a large number of known results.
Coloring (4K1, C4, C6)-free graphs
Irena Penev, ipenev@iuuk.mff.cuni.cz
Charles University, Czech Republic
A graph is even-hole-free if it contains no induced cycles of even length. Even-hole-free graphs
can be recognized in polynomial time, and furthermore, the MAXIMUM CLIQUE problem can
be solved in polynomial time for such graphs. However, the time complexity of the VERTEX
243
Beyond treewidth: the tree-independence number
Martin Milanicˇ, martin.milanic@upr.si
University of Primorska, Slovenia
Coauthors: Clément Dallard, Kenny Štorgel
We introduce a new graph invariant called tree-independence number. This is a common gener-
alization of treewidth and independence number, in the sense that bounded treewidth or bounded
independence number implies bounded tree-independence number. The tree-independence num-
ber of a graph G is defined as the smallest positive integer k such that G has a tree decomposition
whose bags induce subgraphs of G with independence number at most k. While for k = 1 we
obtain the well-known class of chordal graphs, we show that the problem of computing the
tree-independence number of a graph is NP-hard in general.
We consider six graph containment relations (the subgraph, topological minor, and minor
relations, as well as their induced variants) and for each of them completely characterize graph
classes of bounded tree-independence number defined by a single forbidden graph with respect
to the relation. In each of these bounded cases, a tree decomposition with small independence
number can be computed efficiently, which implies polynomial-time solvability of the Maxi-
mum Weight Independent Set (MWIS) problem. This in particular applies to an infinite family
of generalizations of the class of chordal graphs, for which a polynomial-time algorithm for the
MWIS problem was given by Frank in 1976.
Width parameters and graph classes: the case of mim-width
Andrea Munaro, a.munaro@qub.ac.uk
Queen’s University Belfast, United Kingdom
Coauthors: Flavia Bonomo-Braberman, Nick Brettell, Daniël Paulusma, Jake Horsfield,
Giacomo Paesani
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 prob-
lems on special graph classes, it is helpful to know whether the graph class under consideration
has bounded mim-width. We extend the toolkit for proving (un)boundedness of mim-width of
graph classes and initiate a systematic study into bounding mim-width from the perspective
of hereditary graph classes. We present summary theorems of the current state of the art for
the boundedness of mim-width for (H1, H2)-free graphs and observe several interesting conse-
quences. We also study the mim-width of generalized convex graphs. This allows us to re-prove
and strengthen a large number of known results.
Coloring (4K1, C4, C6)-free graphs
Irena Penev, ipenev@iuuk.mff.cuni.cz
Charles University, Czech Republic
A graph is even-hole-free if it contains no induced cycles of even length. Even-hole-free graphs
can be recognized in polynomial time, and furthermore, the MAXIMUM CLIQUE problem can
be solved in polynomial time for such graphs. However, the time complexity of the VERTEX
243
