2026-08-15T06:22:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25150 2026-02-09T08:17:54Z ddc:004 open_access

Bridging Treewidth and Clique-Width via Cograph-Modular-Treewidth Blažej, Václav Jana, Satyabrata Ramanujan, M. S. Strulo, Peter Treewidth Clique-width Cograph FPT W[1]-hard Many classical graph problems - such as Max Cut, Chromatic Number, Edge Dominating Set, and Hamiltonian Cycle - are polynomial-time solvable on cographs, fixed-parameter tractable (FPT) when parameterized by treewidth, but W[1]-hard when parameterized by clique-width. In contrast, Graph Isomorphism is FPT parameterized by treewidth, but for clique-width it is known to be in XP; whether it is FPT or W[1]-hard is open. This reveals a sharp tractability gap between treewidth and clique-width. In this work, we propose a new structural graph parameter, 𝒞-modular-treewidth, which lies between treewidth and clique-width. The parameter leverages modular decomposition and restricts modules to induce graphs from a fixed class 𝒞 (e.g., cographs or edgeless graphs). By exploiting true and false twins - a hallmark of cograph-like structure - our parameter allows the design of efficient algorithms for several hard problems beyond the reach of treewidth-based methods. In this work, we show that 𝒞-modular-treewidth enables efficient solutions under suitable choices of 𝒞, opening a new pathway in the parameterized complexity landscape between treewidth and clique-width. In particular we show that - When parameterized by cograph-modular-treewidth, Isomorphism admits an FPT algorithm, whereas Chromatic Number remains W[1]-hard. - When parameterized by independent-modular-treewidth, Hamiltonian Cycle and Edge Dominating Set remain W[1]-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Václav Blažej and Satyabrata Jana and M. S. Ramanujan and Peter Strulo 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.18 urn:nbn:de:0030-drops-251507 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.18 eng https://creativecommons.org/licenses/by/4.0/legalcode