Please use this identifier to cite or link to this item:
http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/10304
Title: | Robust Contraction Decomposition for Minor-Free Graphs and Its Applications |
Authors: | Bandyapadhyay, Sayan Lochet, William Lokshtanov, Daniel Marx, Dániel Misra, Pranabendu Neuen, Daniel Saurabh, Saket TALE, PRAFULLKUMAR Xue, Jie Dept. of Mathematics |
Keywords: | Graph contraction Graph decomposition Minor-free graphs Planar graphs Subexponential time algorithms 2025-JUL-WEEK3 TOC-JUL-2025 2025 |
Issue Date: | Jun-2026 |
Publisher: | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Citation: | International Colloquium on Automata, Languages, and Programming (ICALP) |
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. |
Description: | Included Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
URI: | https://doi.org/10.4230/LIPIcs.ICALP.2025.17 http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/10304 |
ISBN: | 978-395977372-0 |
ISSN: | 1868-8969 |
Appears in Collections: | CONFERENCE PAPERS |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.