Bonnet, Édouard ;
Chakraborty, Dibyayan ;
Kim, Eun Jung ;
Köhler, Noleen ;
Lopes, Raul ;
Thomassé, Stéphan
TwinWidth VIII: Delineation and WinWins
Abstract
We introduce the notion of delineation. A graph class C is said delineated by twinwidth (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twinwidth if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixedparameter tractable (FPT) exactly when D has bounded twinwidth. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated.
In an effort to draw the delineation frontier between interval graphs (that are delineated) and axisparallel twolengthed segment graphs (that are not), we investigate the twinwidth of restricted segment intersection classes. It was known that (trianglefree) pure axisparallel unit segment graphs have unbounded twinwidth [BGKTW, SODA '21]. We show that K_{t,t}free segment graphs, and axisparallel H_tfree unit segment graphs have bounded twinwidth, where H_t is the halfgraph or ladder of height t. In contrast, axisparallel H₄free twolengthed segment graphs have unbounded twinwidth. We leave as an open question whether unit segment graphs are delineated.
More broadly, we explore which structures (large bicliques, halfgraphs, or independent sets) are responsible for making the twinwidth large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for firstorder model checking on graphs given with O(1)sequences [BKTW, JACM '22], give rise to a variety of algorithmic winwin arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twinwidth on a class C, then p(G) ⩾ k can be decided in FPT time f(k) ⋅ V(G)^O(1). For instance, we readily derive FPT algorithms for kLadder on visibility graphs of 1.5D terrains, and kIndependent Set on visibility graphs of simple polygons. This showcases that the theory of twinwidth can serve outside of classes of bounded twinwidth.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2022.9,
author = {Bonnet, \'{E}douard and Chakraborty, Dibyayan and Kim, Eun Jung and K\"{o}hler, Noleen and Lopes, Raul and Thomass\'{e}, St\'{e}phan},
title = {{TwinWidth VIII: Delineation and WinWins}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {9:19:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772600},
ISSN = {18688969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17365},
URN = {urn:nbn:de:0030drops173650},
doi = {10.4230/LIPIcs.IPEC.2022.9},
annote = {Keywords: Twinwidth, intersection graphs, visibility graphs, monadic dependence and stability, firstorder model checking}
}
14.12.2022
Keywords: 

Twinwidth, intersection graphs, visibility graphs, monadic dependence and stability, firstorder model checking 
Seminar: 

17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 