License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.18
URN: urn:nbn:de:0030-drops-132596
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13259/
Choudhary, Pratibha ;
Kanesh, Lawqueen ;
Lokshtanov, Daniel ;
Panolan, Fahad ;
Saurabh, Saket
Parameterized Complexity of Feedback Vertex Sets on Hypergraphs
Abstract
A feedback vertex set in a hypergraph H is a set of vertices S such that deleting S from H results in an acyclic hypergraph. Here, deleting a vertex means removing the vertex and all incident hyperedges, and a hypergraph is acyclic if its vertex-edge incidence graph is acyclic. We study the (parameterized complexity of) the Hypergraph Feedback Vertex Set (HFVS) problem: given as input a hypergraph H and an integer k, determine whether H has a feedback vertex set of size at most k. It is easy to see that this problem generalizes the classic Feedback Vertex Set (FVS) problem on graphs. Remarkably, despite the central role of FVS in parameterized algorithms and complexity, the parameterized complexity of a generalization of FVS to hypergraphs has not been studied previously. In this paper, we fill this void. Our main results are as follows
- HFVS is W[2]-hard (as opposed to FVS, which is fixed parameter tractable).
- If the input hypergraph is restricted to a linear hypergraph (no two hyperedges intersect in more than one vertex), HFVS admits a randomized algorithm with running time 2^{?(k³log k)}n^{?(1)}.
- If the input hypergraph is restricted to a d-hypergraph (hyperedges have cardinality at most d), then HFVS admits a deterministic algorithm with running time d^{?(k)}n^{?(1)}. The algorithm for linear hypergraphs combines ideas from the randomized algorithm for FVS by Becker et al. [J. Artif. Intell. Res., 2000] with the branching algorithm for Point Line Cover by Langerman and Morin [Discrete & Computational Geometry, 2005].
BibTeX - Entry
@InProceedings{choudhary_et_al:LIPIcs:2020:13259,
author = {Pratibha Choudhary and Lawqueen Kanesh and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh},
title = {{Parameterized Complexity of Feedback Vertex Sets on Hypergraphs}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {18:1--18:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-174-0},
ISSN = {1868-8969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13259},
URN = {urn:nbn:de:0030-drops-132596},
doi = {10.4230/LIPIcs.FSTTCS.2020.18},
annote = {Keywords: feedback vertex sets, hypergraphs, FPT, randomized algorithms}
}
|
Keywords: |
|
feedback vertex sets, hypergraphs, FPT, randomized algorithms |
|
Collection: |
|
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
