Parameterized Algorithms for Deletion to (r,ell)-Graphs

Authors Sudeshna Kolay, Fahad Panolan



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.420.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Sudeshna Kolay
Fahad Panolan

Cite AsGet BibTex

Sudeshna Kolay and Fahad Panolan. Parameterized Algorithms for Deletion to (r,ell)-Graphs. 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. 420-433, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.420

Abstract

For fixed integers r,ell geq 0, a graph G is called an (r,ell)-graph if the vertex set V(G) can be partitioned into r independent sets and ell cliques. This brings us to the following natural parameterized questions: Vertex (r,ell)-Partization and Edge (r,ell)-Partization. An input to these problems consist of a graph G and a positive integer k and the objective is to decide whether there exists a set S subseteq V(G) (S subseteq E(G)) such that the deletion of S from G results in an (r,ell)-graph. These problems generalize well studied problems such as Odd Cycle Transversal, Edge Odd Cycle Transversal, Split Vertex Deletion and Split Edge Deletion. We do not hope to get parameterized algorithms for either Vertex (r, ell)-Partization or Edge (r,ell)-Partization when either of r or ell is at least 3 as the recognition problem itself is NP-complete. This leaves the case of r,ell in {1,2}. We almost complete the parameterized complexity dichotomy for these problems by obtaining the following results: - We show that Vertex (r,ell)-Partization is fixed parameter tractable (FPT) for r,ell in {1,2}. Then we design an Oh(sqrt log n)-factor approximation algorithms for these problems. These approximation algorithms are then utilized to design polynomial sized randomized Turing kernels for these problems. - Edge (r,ell)-Partization is FPT when (r,ell)in{(1,2),(2,1)}. However, the parameterized complexity of Edge (2,2)-Partization remains open. For our approximation algorithms and thus for Turing kernels we use an interesting finite forbidden induced graph characterization, for a class of graphs known as (r,ell)-split graphs, properly containing the class of (r,ell)-graphs. This approach to obtain approximation algorithms could be of an independent interest.
Keywords
  • FPT
  • Turing kernels
  • Approximation algorithms

Metrics

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

References

  1. Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(√log n) approximation algorithms for min uncut, min 2cnf deletion, and directed cut problems. In STOC, pages 573-581, 2005. Google Scholar
  2. Andreas Brandstädt, Van Bang Le, and Thomas Szymczak. The complexity of some problems related to graph 3-colorability, 1998. Google Scholar
  3. Chandra Chekuri, editor. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014. SIAM, 2014. Google Scholar
  4. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. Google Scholar
  5. Stephen A. Cook. The complexity of theorem-proving procedures. In STOC, pages 151-158, New York, NY, USA, 1971. ACM. Google Scholar
  6. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  7. Marek Cygan and Marcin Pilipczuk. Split vertex deletion meets vertex cover: New fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett., 113(5-6):179-182, 2013. Google Scholar
  8. R. Diestel. Graph Theory. Springer, Berlin, second ed., electronic edition, February 2000. Google Scholar
  9. Tomás Feder, Pavol Hell, Sulamita Klein, and Rajeev Motwani. List partitions. STOC, 16:464-472, 2003. Google Scholar
  10. Tomás Feder, Pavol Hell, and Shekoofeh Nekooei Rizi. Partitioning chordal graphs. Electronic Notes in Discrete Mathematics, 38:325-330, 2011. Google Scholar
  11. J. Flum and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006. Google Scholar
  12. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979. Google Scholar
  13. Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, and M. S. Ramanujan. Faster parameterized algorithms for deletion to split graphs. Algorithmica, 71(4):989-1006, 2015. Google Scholar
  14. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci., 72(8):1386-1396, 2006. Google Scholar
  15. András Gyárfás. Generalized split graphs and ramsey numbers. J. Comb. Theory, Ser. A, 81(2):255-261, 1998. Google Scholar
  16. Falk Hüffner. Algorithm engineering for optimal graph bipartization. J. Graph Algorithms Appl., 13(2):77-98, 2009. Google Scholar
  17. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. Linear-time FPT algorithms via network flow. In Chekuri [3], pages 1749-1761. Google Scholar
  18. Stefan Kratsch and Magnus Wahlström. Representative sets and irrelevant vertices: New tools for kernelization. In FOCS, pages 450-459, 2012. Google Scholar
  19. Stefan Kratsch and Magnus Wahlström. Compression via matroids: A randomized polynomial kernel for odd cycle transversal. ACM Transactions on Algorithms, 10(4):20, 2014. Google Scholar
  20. R. Krithika and N. S. Narayanaswamy. Parameterized algorithms for (r, l)-partization. J. Graph Algorithms Appl., 17(2):129-146, 2013. Google Scholar
  21. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms, 11(2):15, 2014. Google Scholar
  22. Daniel Lokshtanov, Saket Saurabh, and Somnath Sikdar. Simpler parameterized algorithm for oct. In Jirí Fiala, Jan Kratochvíl, and Mirka Miller, editors, IWOCA, volume 5874 of Lecture Notes in Computer Science, pages 380-384. Springer, 2009. Google Scholar
  23. Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Transactions on Algorithms, 9(4):30, 2013. Google Scholar
  24. M. S. Ramanujan and Saket Saurabh. Linear time parameterized algorithms via skew-symmetric multicuts. In Chekuri [3], pages 1739-1748. Google Scholar
  25. Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299-301, 2004. 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