Document Open Access Logo

Simultaneous Feedback Edge Set: A Parameterized Perspective

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.5.pdf
  • Filesize: 0.58 MB
  • 13 pages

Document Identifiers

Author Details

Akanksha Agrawal
Fahad Panolan
Saket Saurabh
Meirav Zehavi

Cite As Get BibTex

Akanksha Agrawal, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Simultaneous Feedback Edge Set: A Parameterized Perspective. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.5

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.

Subject Classification

Keywords
  • parameterized complexity
  • feedback edge set
  • alpha-matroid parity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Agrawal, D. Lokshtanov, A. E. Mouawad, and S. Saurabh. Simultaneous feedback vertex set: A parameterized perspective. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS, pages 7:1-7:15, 2016. Google Scholar
  2. Akanksha Agrawal, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Simultaneous feedback edge set: A parameterized perspective. CoRR, abs/1611.07701, 2016. URL: https://arxiv.org/abs/1611.07701.
  3. Noga Alon and Timothy H. Marshall. Homomorphisms of edge-colored graphs and coxeter groups. Journal of Algebraic Combinatorics, 8(1):5-13, 1998. Google Scholar
  4. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics, 12(3):289-297, September 1999. Google Scholar
  5. József Balogh, János Barát, Dániel Gerbner, András Gyárfás, and Gábor N. Sárközy. Partitioning 2-edge-colored graphs by monochromatic paths and cycles. Combinatorica, 34(5):507-526, 2014. Google Scholar
  6. Jørgen Bang-Jensen and Gregory Gutin. Alternating cycles and paths in edge-coloured multigraphs: a survey. Discrete Mathematics, 165:39-60, 1997. Google Scholar
  7. Leizhen Cai and Junjie Ye. Dual connectedness of edge-bicolored graphs and beyond. In Mathematical Foundations of Computer Science, MFCS, volume 8635, pages 141-152, 2014. Google Scholar
  8. W. S. Chou, Yannis Manoussakis, Olga Megalakaki, M. Spyratos, and Zs. Tuza. Paths through fixed vertices in edge-colored graphs. Mathématiques et sciences humaines, 127:49-58, 1994. Google Scholar
  9. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  10. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Joham M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Foundations of Computer Science (FOCS), IEEE 52nd Annual Symposium, pages 150-159, 2011. Google Scholar
  11. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  12. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 764-775, 2016. Google Scholar
  13. M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman &Co., 1979. Google Scholar
  14. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  15. Mikio Kano and Xueliang Li. Monochromatic and heterochromatic subgraphs in edge-colored graphs-a survey. Graphs and Combinatorics, 24(4):237-263, 2008. Google Scholar
  16. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Information Processing Letters, 114(10):556-560, 2014. Google Scholar
  17. Christian Komusiewicz. Tight running time lower bounds for vertex deletion problems. arXiv preprint arXiv:1511.05449, 2015. Google Scholar
  18. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. In Automata, Languages, and Programming, pages 922-934. Springer, 2015. Google Scholar
  19. László Lovász. Matroid matching and some applications. Journal of Combinatorial Theory, Series B, 28(2):208-236, 1980. Google Scholar
  20. Yannis Manoussakis. Alternating paths in edge-colored complete graphs. Discrete Applied Mathematics, 56(2):297-309, 1995. Google Scholar
  21. Dániel Marx. A parameterized view on matroid optimization problems. Theoretical Computer Science, 410(44):4471-4479, October 2009. Google Scholar
  22. Bojan Mohar. Face covers and the genus problem for apex graphs. Journal of Combinatorial Theory, Series B, 82(1):102-117, 2001. Google Scholar
  23. James G Oxley. Matroid theory, volume 3. Oxford University Press, USA, 2006. Google Scholar
  24. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Transactions on Algorithms, (TALG), 6(2):32:1-32:8, 2010. Google Scholar
  25. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the 44th annual ACM symposium on Theory of computing, pages 887-898, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact