Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs

Authors Sudeshna Kolay, Fahad Panolan, Venkatesh Raman, Saket Saurabh



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.75.pdf
  • Filesize: 499 kB
  • 13 pages

Document Identifiers

Author Details

Sudeshna Kolay
Fahad Panolan
Venkatesh Raman
Saket Saurabh

Cite AsGet BibTex

Sudeshna Kolay, Fahad Panolan, Venkatesh Raman, and Saket Saurabh. Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.75

Abstract

For fixed integers r,l >= 0, a graph G is called an (r,l)-graph if the vertex set V(G) can be partitioned into r independent sets and l cliques. Such a graph is also said to have cochromatic number r+l. The class of (r,l) graphs generalizes r-colourable graphs (when l=0) and hence not surprisingly, determining whether a given graph is an (r,l)-graph is NP-hard even when r >= 3 or l >= 3 in general graphs. When r and ell are part of the input, then the recognition problem is NP-hard even if the input graph is a perfect graph (where the Chromatic Number problem is solvable in polynomial time). It is also known to be fixed-parameter tractable (FPT) on perfect graphs when parameterized by r and l. I.e. there is an f(r+l) n^O(1) algorithm on perfect graphs on n vertices where f is a function of r and l. Observe that such an algorithm is unlikely on general graphs as the problem is NP-hard even for constant r and l. In this paper, we consider the parameterized complexity of the following problem, which we call Vertex Partization. Given a perfect graph G and positive integers r,l,k decide whether there exists a set S subset or equal to V(G) of size at most k such that the deletion of S from G results in an (r,l)-graph. This problem generalizes well studied problems such as Vertex Cover (when r=1 and l=0), Odd Cycle Transversal (when r=2, l=0) and Split Vertex Deletion (when r=1=l). 1. Vertex Partization on perfect graphs is FPT when parameterized by k+r+l. 2. The problem, when parameterized by k+r+l, does not admit any polynomial sized kernel, under standard complexity theoretic assumptions. In other words, in polynomial time, the input graph cannot be compressed to an equivalent instance of size polynomial in k+r+l. In fact, our result holds even when k=0. 3. When r,ell are universal constants, then Vertex Partization on perfect graphs, parameterized by k, has a polynomial sized kernel.
Keywords
  • graph deletion
  • FPT algorithms
  • polynomial kernels

Metrics

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

References

  1. Faisal N. Abu-Khzam. A kernelization algorithm for d-hitting set. J. Comput. Syst. Sci., 76(7):524-531, 2010. Google Scholar
  2. Julien Baste, Luerbio Faria, Sulamita Klein, and Ignasi Sau. Parameterized complexity dichotomy for dollar(r, backslashell)dollar-vertex deletion. CoRR, abs/1504.05515, 2015. Google Scholar
  3. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. Google Scholar
  4. Andreas Brandstädt, Van Bang Le, and Thomas Szymczak. The complexity of some problems related to graph 3-colorability. Discrete Applied Mathematics, 89(1–3):59-73, 1998. Google Scholar
  5. 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
  6. Maria Chudnovsky, Neil Robertson, Paul D. Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of Mathematics, 164:51-229, 2006. 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. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  9. Tomas 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. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct pcps for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. 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. András Gyárfás. Generalized split graphs and ramsey numbers. J. Comb. Theory, Ser. A, 81(2):255-261, 1998. Google Scholar
  15. Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization. Inf. Comput., 231:109-116, 2013. Google Scholar
  16. Sudeshna Kolay and Fahad Panolan. Parameterized algorithms for deletion to (r, ell)-graphs. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India, pages 420-433, 2015. Google Scholar
  17. R. Krithika and N. S. Narayanaswamy. Parameterized algorithms for (r, l)-partization. J. Graph Algorithms Appl., 17(2):129-146, 2013. Google Scholar
  18. André E. Kézdy, Hunter S. Snevily, and Chi Wang. Partitioning permutations into increasing and decreasing subsequences. Journal of Combinatorial Theory, Series A, 73(2):353-359, 1996. Google Scholar
  19. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci., 20(2):219-230, 1980. Google Scholar
  20. 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
  21. László Lovász. A characterization of perfect graphs. J. Comb. Theory, Ser. B, 13(2):95-98, 1972. Google Scholar
  22. Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299-301, 2004. URL: http://dx.doi.org/10.1016/j.orl.2003.10.009.
  23. Klaus W. Wagner. Monotonic coverings of finite sets. Elektronische Informationsverarbeitung und Kybernetik, 20(12):633-639, 1984. 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