Simultaneous feedback vertex set: a parameterized perspective

DOI10.4230/LIPICS.STACS.2016.7MaRDI QIDQ4601856zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh

Publication date 24 January 2018

Full work available at URL https://arxiv.org/abs/1510.01557

zbMATH Keywords

edge-colored graphsfeedback vertex setkernelparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: Given a family of graphs $mathcalF$, a graph $G$, and a positive integer $k$, the $mathcalF$-Deletion problem asks whether we can delete at most $k$ vertices from $G$ to obtain a graph in $mathcalF$. $mathcalF$-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A graph $G=(V,cu{p}_{i=1}^{alpha}{E}_i)$, where the edge set of $G$ is partitioned into $alpha$ color classes, is called an $alpha$-edge-colored graph. A natural extension of the $mathcalF$-Deletion problem to edge-colored graphs is the $alpha$-Simultaneous $mathcalF$-Deletion problem. In the latter problem, we are given an $alpha$-edge-colored graph $G$ and the goal is to find a set $S$ of at most $k$ vertices such that each graph $G_{i}setminusS$, where $G_i=(V,E_i)$ and $1leqileqalpha$, is in $mathcalF$. In this work, we study $alpha$-Simultaneous $mathcalF$-Deletion for $mathcalF$ being the family of forests. In other words, we focus on the $alpha$-Simultaneous Feedback Vertex Set ($alpha$-SimFVS) problem. Algorithmically, we show that, like its classical counterpart, $alpha$-SimFVS parameterized by $k$ is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant $alpha$. In particular, we give an algorithm running in $2^{O(alphak)}{n}^{O(1)}$ time and a kernel with $O(alpha{k}^{3(alpha+1)})$ vertices. The running time of our algorithm implies that $alpha$-SimFVS is FPT even when $alphaino(logn)$. We complement this positive result by showing that for $alphainO(logn)$, where $n$ is the number of vertices in the input graph, $alpha$-SimFVS becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).

Recommendations

• Simultaneous feedback vertex set: a parameterized perspective
• scientific article; zbMATH DE number 7278081
• Simultaneous feedback edge set: a parameterized perspective
• Simultaneous feedback edge set: a parameterized perspective
• Generalized pseudoforest deletion: algorithms and uniform kernel

Cited in

(11)

• Simultaneous feedback edge set: a parameterized perspective
• Structural Parameterizations of Feedback Vertex Set
• Simultaneous feedback edge set: a parameterized perspective
• A polyhedral approach to the feedback vertex set problem
• Conflict free feedback vertex set: a parameterized dichotomy
• scientific article; zbMATH DE number 7278081 (Why is no real title available?)
• scientific article; zbMATH DE number 7286685 (Why is no real title available?)
• Simultaneous feedback vertex set: a parameterized perspective
• Assessing the computational complexity of multi-layer subgraph detection
• On parameterized independent feedback vertex set
• On the feedback vertex set polytope of a series-parallel graph

This page was built for publication: Simultaneous feedback vertex set: a parameterized perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601856)