CISPA
Browse
- No file added yet -

A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs

Download (629.96 kB)
conference contribution
posted on 2023-11-29, 18:19 authored by Dániel MarxDániel Marx, Pranabendu Misra, Daniel Neuen, Prafullkumar Tale
Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this paper is to introduce a framework for obtaining n^{O(\sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an n^{O(\sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{\sqrt{k}polylog(k)}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain 2^{\sqrt{k}polylog(k)}n^{O(1)} time (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set. Our algorithms are designed with possible generalization to $H$-minor free graphs in mind. To obtain the same n^{O(\sqrt{k})} time algorithms on H-minor free graphs, the only missing piece is the vertex version of a contraction decomposition theorem that we currently have only for planar graphs.

History

Preferred Citation

Dániel Marx, Pranabendu Misra, Daniel Neuen and Prafullkumar Tale. A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM-SIAM Symposium on Discrete Algorithms (SODA)

Legacy Posted Date

2021-12-14

Open Access Type

  • Gold

BibTeX

@inproceedings{cispa_all_3548, title = "A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs", author = "Marx, Dániel and Misra, Pranabendu and Neuen, Daniel and Tale, Prafullkumar", booktitle="{ACM-SIAM Symposium on Discrete Algorithms (SODA)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC