Abstract
A connected feedback vertex set of a graph is a connected subgraph of the graph whose removal makes the graph cycle free. In this paper, we give an approximation algorithm that computes a connected feedback vertex set of size \((1.9091OPT+6)\) on \(2-\)connected AT-free graphs with running time \(O(n^8m^2)\). Also, we give another approximation algorithm that computes a connected feedback vertex set of size \((2.9091OPT+6)\) on the same graph class with more efficient running time \(O(min\{m(log(n)),n^2\})\).
The second author is a doctoral student at Ramakrishna Mission Vivekananda Educational and Research Institute (RKMVERI) and Institute of Advancing Intelligence (IAI), TCG CREST.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abrishami, T., Chudnovsky, M., Pilipczuk, M., Rzążewski, P., Seymour, P.: Induced subgraphs of bounded treewidth and the container method. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1948–1964. SIAM (2021)
Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math. 12(3), 289–297 (1999)
Balakrishnan, H., Rajaraman, A., Rangan, C.P.: Connected domination and Steiner set on asteroidal triple-free graphs. In: Dehne, F., Sack, J.-R., Santoro, N., Whitesides, S. (eds.) WADS 1993. LNCS, vol. 709, pp. 131–141. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57155-8_242
Belmonte, R., van’t Hof, P., Kamiński, M., Paulusma, D.: The price of connectivity for feedback vertex set. Discret. Appl. Math. 217, 132–143 (2017)
Broersma, H., Kloks, T., Kratsch, D., Müller, H.: Independent sets in asteroidal triple-free graphs. SIAM J. Discret. Math. 12(2), 276–287 (1999)
Chiarelli, N., Hartinger, T.R., Johnson, M., Milanič, M., Paulusma, D.: Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity. Theor. Comput. Sci. 705, 75–83 (2018)
Corneil, D.G., Olariu, S., Stewart, L.: Computing a dominating pair in an asteroidal triple-free graph in linear time. In: Akl, S.G., Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 358–368. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60220-8_76
Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal triple-free graphs. SIAM J. Discret. Math. 10(3), 399–430 (1997)
Dabrowski, K.K., Feghali, C., Johnson, M., Paesani, G., Paulusma, D., Rzążewski, P.: On cycle transversals and their connected variants in the absence of a small linear forest. Algorithmica 82(10), 2841–2866 (2020)
Daniel Liang, Y., Chang, M.-S.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Informatica 34(5) (1997)
Grigoriev, A., Sitters, R.: Connected feedback vertex set in planar graphs. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 143–153. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11409-0_13
Gross, J.L., Yellen, J., Anderson, M.: Graph Theory and its Applications. Chapman and Hall/CRC (2018)
Hartmanis, J.: Computers and intractability: a guide to the theory of np-completeness (Michael R. Garey and David S. Johnson). SIAM Rev. 24(1), 90 (1982)
Kratsch, D.: Domination and total domination on asteroidal triple-free graphs. Discret. Appl. Math. 99(1–3), 111–123 (2000)
Kratsch, D., Müller, H., Todinca, I.: Feedback vertex set on at-free graphs. Discret. Appl. Math. 156(10), 1936–1947 (2008)
Daniel Liang, Y.: On the feedback vertex set problem in permutation graphs. Inf. Process. Lett. 52(3), 123–129 (1994)
Lu, C.L., Tang, C.Y.: A linear-time algorithm for the weighted feedback vertex problem on interval graphs. Inf. Process. Lett. 61(2), 107–111 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Mukherjee, J., Saha, T. (2023). Connected Feedback VertexSet on AT-Free Graphs. In: Hsieh, SY., Hung, LJ., Lee, CW. (eds) Combinatorial Algorithms. IWOCA 2023. Lecture Notes in Computer Science, vol 13889. Springer, Cham. https://doi.org/10.1007/978-3-031-34347-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-031-34347-6_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-34346-9
Online ISBN: 978-3-031-34347-6
eBook Packages: Computer ScienceComputer Science (R0)