Algorithms for subgraph complementation to some classes of graphs

EUROCOMB’23

Dhanyamol Antony Sagartanu Pal R.B. Sandeep

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-006

PDF
Abstract
For a class $\mathcal{G}$ of graphs, the objective of Subgraph Complementation to $\mathcal{G}$ is to find whether there exists a subset $S$ of vertices of the input graph $G$ such that modifying $G$ by complementing the subgraph induced by $S$ results in a graph in $\mathcal{G}$. We obtain a polynomial-time algorithm for the problem when $\mathcal{G}$ is the class of graphs with minimum degree at least $k$, for a constant $k$, answering an open problem by Fomin et al. (Algorithmica, 2020). When $\mathcal{G}$ is the class of graphs without any induced copies of the star graph on $t+1$ vertices (for any constant $t\geq 3$) and diamond, we obtain a polynomial-time algorithm for the problem. This is in contrast with a result by Antony et al. (Algorithmica, 2022) that the problem is NP-complete and cannot be solved in subexponential-time (assuming the Exponential Time Hypothesis) when $\mathcal{G}$ is the class of graphs without any induced copies of the star graph on $t+1$ vertices, for every constant $t\geq 5$.

Pages:
42–49
References

Marcin Kamiński, Vadim V. Lozin, and Martin Milanič. Recent developments on graphs of bounded clique-width. Discret. Appl. Math., 157(12):2747-2761, 2009.
https://doi.org/10.1016/j.dam.2008.08.022

Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, and Dimitrios M. Thilikos. Subgraph complementation. Algorithmica, 82(7):1859-1880, 2020.
https://doi.org/10.1007/s00453-020-00677-8

Dhanyamol Antony, Jay Garchar, Sagartanu Pal, R. B. Sandeep, Sagnik Sen, and

R. Subashini. On subgraph complementation to H-free graphs. Algorithmica, 84(10):2842-2870, 2022.
https://doi.org/10.1007/s00453-022-00991-3

Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep, and R. Subashini. Cutting a tree with subgraph complementation is hard, except for some small trees. In Armando Castañeda and Francisco Rodríguez-Henríquez, editors, LATIN 2022: Theoretical Informatics - 15th Latin American Symposium, Guanajuato, Mexico, November 7-11, 2022, Proceedings, volume 13568 of Lecture Notes in Computer Science, pages 3-19. Springer, 2022.
https://doi.org/10.1007/978-3-031-20624-5_1

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Erik Jan van Leeuwen, and Marcin Wrochna. Polynomial kernelization for removing induced claws and diamonds. Theory Comput. Syst., 60(4):615-636, 2017.
https://doi.org/10.1007/s00224-016-9689-x

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
https://doi.org/10.1007/978-3-319-21275-3

András Gyárfás. Generalized split graphs and ramsey numbers. J. Comb. Theory, Ser. A, 81(2):255-261, 1998.
https://doi.org/10.1006/jcta.1997.2833

Sudeshna Kolay and Fahad Panolan. Parameterized algorithms for deletion to (r, l)- graphs. In Prahladh Harsha and G. Ramalingam, editors, 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, volume 45 of LIPIcs, pages 420-433. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.

Sudeshna Kolay and Fahad Panolan. Parameterized algorithms for deletion to (r, l)- graphs. arXiv preprint arXiv:1504.08120, 2015.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Dhanyamol Antony, Sagartanu Pal, R.B. Sandeep

PDF