2026-07-21T20:02:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23394 2025-10-02T12:53:56Z ddc:004 open_access

Robust Contraction Decomposition for Minor-Free Graphs and Its Applications Bandyapadhyay, Sayan Lochet, William Lokshtanov, Daniel Marx, Dániel Misra, Pranabendu Neuen, Daniel Saurabh, Saket Tale, Prafullkumar Xue, Jie subexponential time algorithms graph decomposition planar graphs minor-free graphs graph contraction We prove a robust contraction decomposition theorem for H-minor-free graphs, which states that given an H-minor-free graph G and an integer p, one can partition in polynomial time the vertices of G into p sets Z₁,… ,Z_p such that tw(G/(Z_i ⧵ Z')) = O(p + |Z'|) for all i ∈ [p] and Z' ⊆ Z_i. Here, tw(⋅) denotes the treewidth of a graph and G/(Z_i ⧵ Z') denotes the graph obtained from G by contracting all edges with both endpoints in Z_i ⧵ Z'. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning E(G), and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time 2^{Õ(√k)} ⋅ n^{O(1)} or n^{O(√k)} for every vertex/edge deletion problems on H-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on H-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on H-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bandyapadhyay and William Lochet and Daniel Lokshtanov and Dániel Marx and Pranabendu Misra and Daniel Neuen and Saket Saurabh and Prafullkumar Tale and Jie Xue 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.17 urn:nbn:de:0030-drops-233948 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.17 eng https://creativecommons.org/licenses/by/4.0/legalcode