2026-07-25T12:07:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19427 2024-03-06T11:04:01Z ddc:004 open_access

Stretch-Width Bonnet, Édouard Duron, Julien Contraction sequences twin-width clique-width algorithms algorithmic metatheorems We introduce a new parameter, called stretch-width, that we show sits strictly between clique-width and twin-width. Unlike the reduced parameters [BKW '22], planar graphs and polynomial subdivisions do not have bounded stretch-width. This leaves open the possibility of efficient algorithms for a broad fragment of problems within Monadic Second-Order (MSO) logic on graphs of bounded stretch-width. In this direction, we prove that graphs of bounded maximum degree and bounded stretch-width have at most logarithmic treewidth. As a consequence, in classes of bounded stretch-width, Maximum Independent Set can be solved in subexponential time 2^{Õ(n^{8/9})} on n-vertex graphs, and, if further the maximum degree is bounded, Existential Counting Modal Logic [Pilipczuk '11] can be model-checked in polynomial time. We also give a polynomial-time O(OPT²)-approximation for the stretch-width of symmetric 0,1-matrices or ordered graphs. Somewhat unexpectedly, we prove that exponential subdivisions of bounded-degree graphs have bounded stretch-width. This allows to complement the logarithmic upper bound of treewidth with a matching lower bound. We leave as open the existence of an efficient approximation algorithm for the stretch-width of unordered graphs, if the exponential subdivisions of all graphs have bounded stretch-width, and if graphs of bounded stretch-width have logarithmic clique-width (or rank-width). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Julien Duron 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.8 urn:nbn:de:0030-drops-194279 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.8 eng https://creativecommons.org/licenses/by/4.0/legalcode