A polynomial kernel for block graph deletion. (English) Zbl 1372.68134
Summary: In the Block Graph Deletion problem, we are given a graph \(G\) on \(n\) vertices and a positive integer \(k\), and the objective is to check whether it is possible to delete at most \( k\) vertices from \( G\) to make it a block graph, i.e., a graph in which each block is a clique. In this paper, we obtain a kernel with \({\mathcal {O}}(k^{6})\) vertices for the Block Graph Deletion problem. This is a first step to investigate polynomial kernels for deletion problems into non-trivial classes of graphs of bounded rank-width, but unbounded tree-width. Our result also implies that Chordal Vertex Deletion admits a polynomial-size kernel on diamond-free graphs. For the kernelization and its analysis, we introduce the notion of ‘complete degree’ of a vertex. We believe that the underlying idea can be potentially applied to other problems. We also prove that the Block Graph Deletion problem can be solved in time \(10^{k}\cdot n^{{\mathcal {O}}(1)}\).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Software:
Algorithm 447References:
| [1] | Agrawal, A., Kolay, S., Lokshtanov, D., Saurabh, S.: A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion, pp. 1-13. Springer, Berlin (2016) · Zbl 1417.68145 |
| [2] | Agrawal, A., Lokshtanov, D., Misra, P., Saurabh, S., Zehavi, M.: Feedback vertex set inspired kernel for chordal vertex deletion. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pp. 1383-1398. Society for Industrial and Applied Mathematics, Philadelphia (2017) · Zbl 1410.68270 |
| [3] | Bodlaender, H.L.: On disjoint cycles. In: Proceedings of the 17th International Workshop, WG ’91, pp. 230-238. Springer, London (1992) · Zbl 0815.05040 |
| [4] | Bonnet, É., Brettell, N., Kwon, O., Marx, D.: Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property, pp. 233-244. Springer, Berlin (2016) · Zbl 1417.68062 |
| [5] | Cao, Y., Chen, J., Liu, Y.: On feedback vertex set: New measure and new structures. Algorithmica 73(1), 63-86 (2015) · Zbl 1327.05318 |
| [6] | Cao, Y., Marx, D.: Chordal editing is fixed-parameter tractable. Algorithmica 75(1), 118-137 (2016) · Zbl 1344.68095 · doi:10.1007/s00453-015-0014-x |
| [7] | 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) · Zbl 1152.68055 · doi:10.1016/j.jcss.2008.05.002 |
| [8] | Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12-75 (1990) · Zbl 0722.03008 · doi:10.1016/0890-5401(90)90043-H |
| [9] | Cygan, M.; Pilipczuk, M.; Pilipczuk, M.; Wojtaszczyk, J.; Raman, V. (ed.); Saurabh, S. (ed.), An improved fpt algorithm and quadratic kernel for pathwidth one vertex deletion, 95-106 (2010), Berlin · Zbl 1309.68090 · doi:10.1007/978-3-642-17493-3_11 |
| [10] | Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time (extended abstract). In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pp. 150-159. IEEE Computer Society, Los Alamitos (2011) · Zbl 1292.68122 |
| [11] | Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discret. Math. 27(1), 290-309 (2013) · Zbl 1268.05196 · doi:10.1137/110843071 |
| [12] | Dehne, F., Fellows, M., Langston, M., Rosamond, F., Stevens, K.: An \[{O}(2^{O(k)}n^3)O\](2O(k)n3) fpt algorithm for the undirected feedback vertex set problem. Theory Comput. Syst. 41(3), 479-492 (2007) · Zbl 1148.68037 · doi:10.1007/s00224-007-1345-z |
| [13] | Downey, R., Fellows, M.: Fixed-parameter tractability and completeness. III. Some structural aspects of the W hierarchy. In: Ambos-Spies, K., Homer, S., Schöning, U. (eds.) Complexity Theory, pp. 191-225. Cambridge University Press, Cambridge (1993) · Zbl 0799.68087 |
| [14] | Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, 20-23 Oct 2012, pp. 470-479 (2012) |
| [15] | Gallai, T.: Maximum-minimum Sätze und verallgemeinerte Faktoren von Graphen. Acta Math. Acad. Sci. Hungar. 12, 131-173 (1961) · Zbl 0142.41404 · doi:10.1007/BF02066678 |
| [16] | Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386-1396 (2006) · Zbl 1119.68134 · doi:10.1016/j.jcss.2006.02.001 |
| [17] | Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372-378 (1973) · doi:10.1145/362248.362272 |
| [18] | Jansen, B.M.P., Pilipczuk, M.: Approximation and kernelization for chordal vertex deletion. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pp. 1399-1418. Society for Industrial and Applied Mathematics, Philadelphia (2017) · Zbl 1410.68300 |
| [19] | Kim, E.J., Kwon, O.: A Polynomial Kernel for Block Graph Deletion. In: Husfeldt, T., Kanj, I. (eds.) 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 43, pp. 270-281. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2015) · Zbl 1372.68133 |
| [20] | Kanj, I.; Pelsmajer, M.; Schaefer, M.; Downey, R. (ed.); Fellows, M. (ed.); Dehne, F. (ed.), Parameterized algorithms for feedback vertex set, 235-247 (2004), Berlin · Zbl 1104.68541 · doi:10.1007/978-3-540-28639-4_21 |
| [21] | Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms, 12(2):Art. 21, 41 (2016) · Zbl 1336.68201 |
| [22] | Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556-560 (2014) · Zbl 1371.68116 · doi:10.1016/j.ipl.2014.05.001 |
| [23] | Misra, N., Philip, G., Raman, V., Saurabh, S.: On parameterized independent feedback vertex set. Theor. Comput. Sci. 461(0):65-75 (2012). 17th International Computing and Combinatorics Conference (COCOON 2011) · Zbl 1253.68181 |
| [24] | Oum, S.: Rank-width and vertex-minors. J. Comb. Theory Ser. B 95(1), 79-100 (2005) · Zbl 1070.05023 · doi:10.1016/j.jctb.2005.03.003 |
| [25] | Raman, V., Saurabh, S., Subramanian, C.R.: Faster fixed parameter tractable algorithms for undirected feedback vertex set. In: Bose, P., Morin, P. (eds.) Algorithms and Computation, Volume 2518 of Lecture Notes in Computer Science, pp. 241-248. Springer, Berlin (2002) · Zbl 1019.68082 |
| [26] | Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299-301 (2004) · Zbl 1052.05061 · doi:10.1016/j.orl.2003.10.009 |
| [27] | Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309-322 (1986) · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4 |
| [28] | Thomassé., S.: A \[4{k}^24\] k2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32:1-32:8 (2010) · Zbl 1300.05236 · doi:10.1145/1721837.1721848 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
