Sponsor
Bandyapadhyay, Sayan: The work has been supported by the NSF grant 2311397. Misra, Pranabendu: Supported by SERB StartUp Grant.
Published In
Leibniz International Proceedings in Informatics Lipics
Document Type
Conference Proceeding
Publication Date
6-30-2025
Subjects
Graph Clustering, Graph Programs (Computer program language)
Abstract
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.
Rights
Copyright (c) 2025 The Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.
Locate the Document
https://doi.org/10.4230/LIPIcs.ICALP.2025.17
DOI
10.4230/LIPIcs.ICALP.2025.17
Persistent Identifier
https://archives.pdx.edu/ds/psu/43959
Citation Details
Bandyapadhyay, S., Lochet, W., Lokshtanov, D., Marx, D., Misra, P., Neuen, D., ... & Xue, J. (2024). Robust Contraction Decomposition for Minor-Free Graphs and its Applications. arXiv preprint arXiv:2412.04145.