Document Open Access Logo

Strong Parameterized Deletion: Bipartite Graphs

Authors Ashutosh Rai, M. S. Ramanujan

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2016.21.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • fixed parameter tractable
  • bipartite-editing
  • recursive understanding

Metrics

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

Abstract

The purpose of this article is  two fold: (a) to formally introduce a stronger version of graph deletion problems; and (b) to study this version in the context of bipartite graphs. Given a  family  of graphs F, a typical instance of parameterized graph deletion problem consists of an undirected graph G and a positive integer k and the objective is to check whether we can delete at most k vertices (or k edges) such that the resulting graph belongs to F. Another version that has been recently studied is the one where the input contains two integers k and l and the objective is to check whether we can delete at most k vertices and l edges such that the resulting graph belongs to F. In this paper, we propose and initiate the study of a more general version which we call strong deletion. In this problem, given an undirected graph G and positive integers k and l, the objective is to check whether there exists a vertex subset S of size at most k such that each  connected component of G-S can be transformed into a graph in F by deleting at most l edges. In this paper we study this stronger version of deletion problems for the class of bipartite graphs. In particular, we study Strong Bipartite Deletion, where given an undirected graph G and positive integers k and l, the objective is to check whether there exists a vertex subset S of size at most k such that each  connected component of G-S can be made bipartite by deleting at most l edges. While fixed-parameter tractability when parameterizing by k or l alone is unlikely, we show that this problem is fixed-parameter tractable (FPT) when parameterized by both k and l.

Cite As Get BibTex

Ashutosh Rai and M. S. Ramanujan. Strong Parameterized Deletion: Bipartite Graphs. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.21

Author Details

Ashutosh Rai
M. S. Ramanujan

References

  1. Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. Simultaneous Feedback Vertex Set: A Parameterized Perspective. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.7.
  2. Leizhen Cai. Parameterized complexity of vertex colouring. Discrete Applied Mathematics, 127(3):415-429, 2003. Google Scholar
  3. Yixin Cao. Unit interval editing is fixed-parameter tractable. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 306-317. Springer, 2015. Google Scholar
  4. Yixin Cao. Linear recognition of almost interval graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1096-1115, 2016. Google Scholar
  5. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms, 11(3):21:1-21:35, 2015. Google Scholar
  6. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118-137, 2016. Google Scholar
  7. Rajesh Hemant Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 460-469, 2012. Google Scholar
  8. Michael R. Fellows, Bart M. P. Jansen, and Frances A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb., 34(3):541-566, 2013. Google Scholar
  9. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In FOCS, 2012. Google Scholar
  10. Toshihiro Fujito. A unified approximation algorithm for node-deletion problems. Discrete Appl. Math., 86:213-231, September 1998. URL: http://dx.doi.org/10.1016/S0166-218X(98)00035-3.
  11. Robert Ganian, M. S. Ramanujan, and Stefan Szeider. Discovering archipelagos of tractability for constraint satisfaction and counting. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1670-1681, 2016. Google Scholar
  12. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 479-488, 2011. Google Scholar
  13. Bart M. P. Jansen. The power of data reduction: Kernels for fundamental graph problems. Ph.D. Thesis, 2013. Google Scholar
  14. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1802-1811, 2014. Google Scholar
  15. Ken-ichi Kawarabayashi and Mikkel Thorup. The minimum k-way cut of bounded size is fixed-parameter tractable. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 160-169, 2011. Google Scholar
  16. Eun Jung Kim and O.-joung Kwon. A polynomial kernel for block graph deletion. In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, volume 43 of LIPIcs, pages 270-281, 2015. Google Scholar
  17. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 613-624, 2013. Google Scholar
  18. 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. URL: http://dx.doi.org/10.1016/0022-0000(80)90060-4.
  19. 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:1-15:31, 2014. Google Scholar
  20. Daniel Lokshtanov and M. S. Ramanujan. Parameterized tractability of multiway cut with parity constraints. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 750-761, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_63.
  21. Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. J. ACM, 41:960-981, September 1994. URL: http://dx.doi.org/10.1145/185675.306789.
  22. 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
  23. Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. Generalized pseudoforest deletion: Algorithms and uniform kernel. In Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, volume 9235 of Lecture Notes in Computer Science, pages 517-528. Springer, 2015. Google Scholar
  24. Marcin Pilipczuk, Michal Pilipczuk, and Marcin Wrochna. Edge bipartization faster than 2^k. In 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, LIPIcs, 2016. Google Scholar
  25. Ashutosh Rai, M. S. Ramanujan, and Saket Saurabh. A parameterized algorithm for mixed-cut. In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, pages 672-685, 2016. Google Scholar
  26. Mihalis Yannakakis. Node-and edge-deletion NP-complete problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, STOC'78, pages 253-264, New York, NY, USA, 1978. ACM. URL: http://dx.doi.org/10.1145/800133.804355.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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