Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Bounding the mim-width of hereditary graph classes

Brettell, N. and Horsfield, J. and Munaro, A. and Paesani, G. and Paulusma, D. (2022) 'Bounding the mim-width of hereditary graph classes.', Journal of Graph Theory, 99 (1). pp. 117-151.

Abstract

A large number of NP-hard 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 mim-width, 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 mim-width of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes, and make a comparison with clique-width, a more restrictive width parameter that has been well studied. We prove that for a given graph H, the class of H-free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for (H1, H2)-free graphs. We identify several general classes of (H1, H2)-free graphs having unbounded clique-width, but bounded mim-width; moreover, we show that a branch decomposition of constant mim-width can be found in polynomial time for these classes. Hence, these results have algorithmic implications: when the input is restricted to such a class of (H1, H2)-free graphs, many problems become polynomial-time solvable, including classical problems such as k-Colouring and Independent Set, domination-type problems known as LC-VSVP problems, and distance versions of LC-VSVP problems, to name just a few. We also prove a number of new results showing that, for certain H1 and H2, the class of (H1, H2)-free graphs has unbounded mim-width. Boundedness of clique-width implies boundedness of mim-width. By combining our results with the known bounded cases for clique-width, we present summary theorems of the current state of the art for the boundedness of mim-width for (H1, H2)-free graphs. In particular, we classify the mim-width of (H1, H2)-free graphs for all pairs (H1, H2) with |V (H1)| + |V (H2)| ≤ 8. When H1 and H2 are connected graphs, we classify all pairs (H1, H2) except for one remaining infinite family and a few isolated cases.

Item Type:Article
Full text:Publisher-imposed embargo until 25 August 2022.
(AM) Accepted Manuscript
File format - PDF
(644Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1002/jgt.22730
Publisher statement:This is the peer reviewed version of the following article: Brettell, N., Horsfield, J., Munaro, A., Paesani, G. & Paulusma, D. (2022). Bounding the mim-width of hereditary graph classes. Journal of Graph Theory 99(1): 117-151, which has been published in final form at https://doi.org/10.1002/jgt.22730. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited.
Date accepted:15 July 2021
Date deposited:24 August 2021
Date of first online publication:25 August 2021
Date first made open access:25 August 2022

Save or Share this output

Export:
Export
Look up in GoogleScholar