Finding Even Subgraphs Even Faster

Authors Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, Saket Saurabh



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.434.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Prachi Goyal
Pranabendu Misra
Fahad Panolan
Geevarghese Philip
Saket Saurabh

Cite AsGet BibTex

Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Finding Even Subgraphs Even Faster. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 434-447, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.434

Abstract

Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k edges(arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees--where the resulting graph is Eulerian,the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al.[Algorithmica, 2014] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time 2^O(k log k)n^O(1). They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time 2^O(k)n^O(1). It was also posed as an open problem at the School on Parameterized Algorithms and Complexity 2014, Bedlewo, Poland. In this paper we answer their question in the affirmative: using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2^O(k)n^O(1). The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.
Keywords
  • Eulerian Edge Deletion
  • FPT
  • Representative Family.

Metrics

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

References

  1. Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs: Theory, Algorithms and Applications. Springer Publishing Company, Incorporated, 2nd edition, 2008. Google Scholar
  2. Leizhen Cai and Boting Yang. Parameterized complexity of even/odd subgraph problems. J. Discrete Algorithms, 9(3):231-240, 2011. Google Scholar
  3. Marek Cygan, Fedor Fomin, Bart M. P. Jansen, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Open Problems for FPT School 2014, Bȩdlewo, Poland. URL: http://fptschool.mimuw.edu.pl/opl.pdf.
  4. Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Ildikó Schlotter. Parameterized complexity of eulerian deletion problems. Algorithmica, 68(1):41-61, 2014. Google Scholar
  5. Konrad K Dabrowski, Petr A Golovach, Pim van’t Hof, and Daniël Paulusma. Editing to eulerian graphs. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science(FSTTCS), 2014. Google Scholar
  6. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 2010. Google Scholar
  7. Jack Edmonds and Ellis L. Johnson. Matching, euler tours and the Chinese postman. Mathematical Programming, 5(1):88-124, 1973. Google Scholar
  8. Fedor V. Fomin and Petr A. Golovach. Long circuits and large euler subgraphs. In ESA, volume 8125, pages 493-504, 2013. Google Scholar
  9. Fedor V. Fomin and Petr A. Golovach. Parameterized complexity of connected even/odd subgraph problems. J. Comput. Syst. Sci., 80(1):157-179, 2014. Google Scholar
  10. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In SODA, pages 142-151, 2014. Google Scholar
  11. András Frank. A survey on T-joins, T-cuts, and conservative weightings. In Combinatorics, Paul Erdös is eighty, volume 2, pages 213-252. János Bolyai Mathematical Society, 1993. Google Scholar
  12. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012), pages 450-459. IEEE, 2012. Google Scholar
  13. Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, and Saket Saurabh. Deterministic truncation of linear matroids. In Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, (ICALP 2015), pages 922-934, 2015. Google Scholar
  14. Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci, 410(44):4471-4479, 2009. Google Scholar
  15. B. Monien. How to find long paths efficiently. Ann. Discrete Math., 25:239-254, 1985. Google Scholar
  16. James G Oxley. Matroid theory, volume 3. Oxford University Press, 2006. Google Scholar
  17. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC 2012), pages 887-898. ACM, 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