Skip to main content
Erschienen in:
Buchtitelbild

2016 | OriginalPaper | Buchkapitel

A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion

verfasst von : Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov, Saket Saurabh

Erschienen in: LATIN 2016: Theoretical Informatics

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A graph G is called a block graph if every maximal 2-connected component of G is a clique. In this paper we study the Block Graph Vertex Deletion from the perspective of fixed parameter tractable (FPT) and kernelization algorithms. In particular, an input to Block Graph Vertex Deletion consists of a graph G and a positive integer k, and the objective to check whether there exists a subset \(S \subseteq V(G)\) of size at most k such that the graph induced on \(V(G) \setminus S\) is a block graph. In this paper we give an FPT algorithm with running time \(4^kn^{\mathcal {O}(1)}\) and a polynomial kernel of size \(\mathcal {O}(k^4)\) for Block Graph Vertex Deletion. The running time of our FPT algorithm improves over the previous best algorithm for the problem that runs in time \(10^kn^{\mathcal {O}(1)}\), and the size of our kernel reduces over the previously known kernel of size \(\mathcal {O}(k^6)\). Our results are based on a novel connection between Block Graph Vertex Deletion and the classical Feedback Vertex Set problem in graphs without induced \(C_4\) and \(K_4-e\). To achieve our results we also obtain an algorithm for Weighted Feedback Vertex Set running in time \(3.618^kn^{\mathcal {O}(1)}\) and improving over the running time of previously known algorithm with running time \(5^kn^{\mathcal {O}(1)}\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat 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)MathSciNetCrossRefMATH 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)MathSciNetCrossRefMATH
2.
Zurück zum Zitat Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)CrossRefMATH Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)CrossRefMATH
3.
Zurück zum Zitat Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188–1198 (2008)MathSciNetCrossRefMATH Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188–1198 (2008)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)CrossRefMATH Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)CrossRefMATH
5.
Zurück zum Zitat Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)MATH Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)MATH
6.
Zurück zum Zitat Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, New York (2006)MATH Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, New York (2006)MATH
7.
Zurück zum Zitat Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S., F-deletion, P.: Approximation, kernelization and optimal FPT algorithms. In: FOCS (2012) Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S., F-deletion, P.: Approximation, kernelization and optimal FPT algorithms. In: FOCS (2012)
11.
12.
Zurück zum Zitat Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980)MathSciNetCrossRefMATH Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980)MathSciNetCrossRefMATH
14.
Zurück zum Zitat Marx, D., O’Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30 (2013)MathSciNetCrossRefMATH Marx, D., O’Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30 (2013)MathSciNetCrossRefMATH
16.
Zurück zum Zitat Tong, P., Lawler, E.L., Vazirani, V.V.: Solving the weighted parity problem for gammoids by reduction to graphic matching. Technical report UCB/CSD-82-103, EECS Department, University of California, Berkeley, April 1982 Tong, P., Lawler, E.L., Vazirani, V.V.: Solving the weighted parity problem for gammoids by reduction to graphic matching. Technical report UCB/CSD-82-103, EECS Department, University of California, Berkeley, April 1982
Metadaten
Titel
A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
verfasst von
Akanksha Agrawal
Sudeshna Kolay
Daniel Lokshtanov
Saket Saurabh
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-49529-2_1