License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.5
URN: urn:nbn:de:0030-drops-67767
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6776/
Go to the corresponding LIPIcs Volume Portal


Agrawal, Akanksha ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

Simultaneous Feedback Edge Set: A Parameterized Perspective

pdf-format:
LIPIcs-ISAAC-2016-5.pdf (0.6 MB)


Abstract

In a recent article Agrawal et al. (STACS 2016) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). In this problem the input is an n-vertex graph G, an integer k and a coloring function col : E(G) -> 2^[alpha] , and the objective is to check whether there exists a vertex subset S of cardinality at most k in G such that for all i in [alpha], G_i - S is acyclic. Here, G_i = (V (G), {e in E(G) | i in col(e)}) and [alpha] = {1,...,alpha}. In this paper we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (Sim-FES). In this problem, the input is same as the input of Sim-FVS and the objective is to check whether there is an edge subset S of cardinality at most k in G such that for all i in [alpha], G_i - S is acyclic. Unlike the vertex variant of the problem, when alpha = 1, the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for alpha = 3 Sim-FES is NP-hard by giving a reduction from Vertex Cover on cubic-graphs. The same reduction shows that the problem does not admit an algorithm of running time O(2^o(k) n^O(1)) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time O(2^((omega k alpha) + (alpha log k)) n^O(1)), where omega is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when alpha = 2. We also give a kernel for Sim-FES with (k alpha)^O(alpha) vertices. Finally, we consider the problem Maximum Simultaneous Acyclic Subgraph. Here, the input is a graph G, an integer q and, a coloring function col : E(G) -> 2^[alpha] . The question is whether there is a edge subset F of cardinality at least q in G such that for all i in [alpha], G[F_i] is acyclic. Here, F_i = {e in F | i in col(e)}. We give an FPT algorithm for Maximum Simultaneous Acyclic Subgraph running in time O(2^(omega q alpha) n^O(1) ). All our algorithms are based on parameterized version of the Matroid Parity problem.

BibTeX - Entry

@InProceedings{agrawal_et_al:LIPIcs:2016:6776,
  author =	{Akanksha Agrawal and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
  title =	{{Simultaneous Feedback Edge Set: A Parameterized Perspective}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6776},
  URN =		{urn:nbn:de:0030-drops-67767},
  doi =		{10.4230/LIPIcs.ISAAC.2016.5},
  annote =	{Keywords: parameterized complexity, feedback edge set, alpha-matroid parity}
}

Keywords: parameterized complexity, feedback edge set, alpha-matroid parity
Seminar: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 02.12.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI