Characterizations and recognition algorithms for distance-hereditary graphs partitionable into a stable set and a forest

Maria Luíza López da Cruz; Victor Rangel Ramos; Rodolfo A. Oliveira; Raquel S. F. Bravo; Uéverton S. Souza

doi:10.5753/jbcs.2025.5191

Authors

Maria Luíza López da Cruz Fluminense Federal University https://orcid.org/0009-0001-5611-5574
Victor Rangel Ramos Fluminense Federal University https://orcid.org/0000-0001-5231-8289
Rodolfo A. Oliveira Fluminense Federal University https://orcid.org/0000-0002-8278-8465
Raquel S. F. Bravo Fluminense Federal University https://orcid.org/0000-0002-2572-1977
Uéverton S. Souza Fluminense Federal University https://orcid.org/0000-0002-5320-9209

DOI:

https://doi.org/10.5753/jbcs.2025.5191

Keywords:

Near-Bipartiteness, Feedback Vertex Set, Stable Set, Independent Feedback Vertex, Distance-Hereditary Graphs

Abstract

Given a simple graph G=(V, E), the Near-Bipartiteness problem asks whether V(G) can be partitioned into two sets S and F such that S is a stable set and F induces a forest. Alternatively, the Near-Bipartiteness problem can be seen as the problem of determining whether G admits an independent feedback vertex set S. Since such a problem is NP-complete even for perfect graphs, in this paper, our goal is to study the property of being near-bipartite on distance-hereditary graphs, a well-known subclass of perfect graphs. We show that there is an infinite set of minimal forbidden subgraphs for a distance-hereditary graph to be near-bipartite. In addition, we present a finite set of forbidden subgraphs that give us a sufficient condition for the existence of a near-bipartition in such a graph class. Finally, by using one-vertex-extension trees, we present a linear-time algorithm for the Near-Bipartiteness problem on distance-hereditary graphs.

Downloads

Download data is not yet available.

References

Agrawal, A., Gupta, S., Saurabh, S., and Sharma, R. (2017). Improved algorithms and combinatorial bounds for independent feedback vertex set. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. DOI: 10.4230/LIPIcs.IPEC.2016.2.

Bandelt, H.-J. and Mulder, H. M. (1986). Distance-hereditary graphs. Journal of Combinatorial Theory, Series B, 41(2):182-208. DOI: 10.1016/0095-8956(86)90043-2.

Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2017). Recognizing graphs close to bipartite graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. DOI: 10.4230/LIPIcs.MFCS.2017.70.

Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131:26-32. DOI: 10.1016/j.ipl.2017.11.004.

Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2019). Independent feedback vertex set for p5-free graphs. Algorithmica, 81(4):1342-1369. DOI: 10.1007/s00453-018-0474-x.

Bondy, J. A., Murty, U. S. R., et al. (1976). Graph theory with applications, volume 290. Macmillan London. Book.

Brandstädt, A., Brito, S., Klein, S., Nogueira, L. T., and Protti, F. (2013). Cycle transversals in perfect graphs and cographs. Theoretical Computer Science, 469:15-23. DOI: 10.1016/j.tcs.2012.10.030.

Bravo, R., Oliveira, R., da Silva, F., and Souza, U. S. (2023). Partitioning p4-tidy graphs into a stable set and a forest. Discrete Applied Mathematics, 338:22-29. DOI: 10.1016/j.dam.2023.05.016.

Chang, M.-S., Hsieh, S.-Y., and Chen, G.-H. (1997). Dynamic programming on distance-hereditary graphs. In International Symposium on Algorithms and Computation, pages 344-353. Springer. DOI: 10.1007/3-540-63890-3_37.

Courcelle, B. (1990). The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12 - 75. DOI: 10.1016/0890-5401(90)90043-H.

Courcelle, B., Makowsky, J., and Rotics, U. (2000). Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150. DOI: 10.1007/s002249910009.

da Cruz, M. L. L., Bravo, R. S. F., Oliveira, R., and Souza, U. S. (2023). Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets. In Wu, W. and Guo, J., editors, Combinatorial Optimization and Applications - 17th International Conference, COCOA 2023, Hawaii, HI, USA, December 15-17, 2023, Proceedings, Part I, volume 14461 of Lecture Notes in Computer Science, pages 82-93. Springer. DOI: 10.1007/978-3-031-49611-0_6.

Dross, F., Montassier, M., and Pinlou, A. (2017). Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. European Journal of Combinatorics, 66:81-94. DOI: 10.1016/j.ejc.2017.06.014.

Flum, J. and Grohe, M. (2006). Parameterized complexity theory. Texts Theoret. Comput. Sci. EATCS Ser. DOI: 10.1007/3-540-29953-X.

Golumbic, M. and Rotics, U. (2000). On the clique-width of some perfect graph classes. International Journal of Foundations of Computer Science, 11(3):423-443. DOI: 10.1142/S0129054100000260.

Grötschel, M., Lovász, L., and Schrijver, A. (1984). Polynomial algorithms for perfect graphs. Ann. Discrete Math, 21:325-356. DOI: 10.1016/S0304-0208(08)72943-8.

Howorka, E. (1977). A characterization of distance-hereditary graphs. The quarterly journal of mathematics, 28(4):417-420. DOI: 10.1093/qmath/28.4.417.

Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Springer. DOI: 10.1007/978-1-4684-2001-2_9.

Misra, N., Philip, G., Raman, V., and Saurabh, S. (2012). On parameterized independent feedback vertex set. Theoretical Computer Science, 461:65-75. DOI: 10.1016/j.tcs.2012.02.012.

Smith, G. and Walford, R. (1975). The identification of a minimal feedback vertex set of a directed graph. IEEE Transactions on Circuits and Systems, 22(1):9-15. DOI: 10.1109/TCS.1975.1083961.