Parameterized complexity of feedback vertex sets on hypergraphs

Choudhary, P. and Kanesh, L. and Lokshtanov, D. and Panolan, Fahad and et al, . (2020) Parameterized complexity of feedback vertex sets on hypergraphs. In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, 14-18 December 2020, Virtual, Goa.

Full text not available from this repository. (Request a copy)

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 W2-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 2O(k3 log k)nO(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 dO(k)nO(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. Â© Pratibha Choudhary, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh; licensed under Creative Commons License CC-BY.

[error in script]

IITH Creators:

IITH Creators	ORCiD
Panolan, Fahad	https://orcid/org/0000-0001-6213-8687

Item Type:

Conference or Workshop Item (Paper)

Additional Information:

Funding Saket Saurabh: Received funding from European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant no. 819416), and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Uncontrolled Keywords:

Feedback vertex sets, FPT, Hypergraphs, Randomized algorithms

Subjects:

Computer science

Divisions:

Department of Computer Science & Engineering

Depositing User:

. LibTrainee 2021

Date Deposited:

15 Nov 2022 07:52

Last Modified:

16 Nov 2022 06:38