Brettell, Nick ;
Horsfield, Jake ;
Munaro, Andrea ;
Paesani, Giacomo ;
Paulusma, Daniël
Bounding the MimWidth of Hereditary Graph Classes
Abstract
A large number of NPhard graph problems are solvable in XP time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In this paper we consider mimwidth, a particularly general width parameter that has a number of algorithmic applications whenever a decomposition is "quickly computable" for the graph class under consideration.
We start by extending the toolkit for proving (un)boundedness of mimwidth of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mimwidth from the perspective of hereditary graph classes, and make a comparison with cliquewidth, a more restrictive width parameter that has been well studied.
We prove that for a given graph H, the class of Hfree graphs has bounded mimwidth if and only if it has bounded cliquewidth. We show that the same is not true for (H₁,H₂)free graphs. We identify several general classes of (H₁,H₂)free graphs having unbounded cliquewidth, but bounded mimwidth, illustrating the power of mimwidth. Moreover, we show that a branch decomposition of constant mimwidth can be found in polynomial time, for these classes. Hence, as mentioned, these results have algorithmic implications: when the input is restricted to such a class of (H₁,H₂)free graphs, many problems become polynomialtime solvable, including classical problems such as kColouring and Independent Set, dominationtype problems known as LCVSVP problems, and distance versions of LCVSVP problems, to name just a few. We also prove a number of new results showing that, for certain H₁ and H₂, the class of (H₁,H₂)free graphs has unbounded mimwidth.
Boundedness of cliquewidth implies boundedness of mimwidth. By combining our results, which give both new bounded and unbounded cases for mimwidth, with the known bounded cases for cliquewidth, we present summary theorems of the current state of the art for the boundedness of mimwidth for (H₁,H₂)free graphs. In particular, we classify the mimwidth of (H₁,H₂)free graphs for all pairs (H₁,H₂) with V(H₁) + V(H₂) ≤ 8. When H₁ and H₂ are connected graphs, we classify all pairs (H₁,H₂) except for one remaining infinite family and a few isolated cases.
BibTeX  Entry
@InProceedings{brettell_et_al:LIPIcs:2020:13309,
author = {Nick Brettell and Jake Horsfield and Andrea Munaro and Giacomo Paesani and Dani{\"e}l Paulusma},
title = {{Bounding the MimWidth of Hereditary Graph Classes}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {6:16:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771726},
ISSN = {18688969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13309},
URN = {urn:nbn:de:0030drops133099},
doi = {10.4230/LIPIcs.IPEC.2020.6},
annote = {Keywords: Width parameter, mimwidth, cliquewidth, hereditary graph class}
}
04.12.2020
Keywords: 

Width parameter, mimwidth, cliquewidth, hereditary graph class 
Seminar: 

15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 