Explicit linear kernels for packing problems. (English) Zbl 1422.68111
Summary: During the last years, several algorithmic meta-theorems have appeared [H. L. Bodlaender et al., in: Proceedings of the 50th annual IEEE symposium on foundations of computer science, FOCS’09. Los Alamitos, CA: IEEE Computer Society. 629–638 (2009; Zbl 1292.68089); F. V. Fomin et al., in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA’10. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 503–510 (2010; Zbl 1288.68116); E. J. Kim et al., ACM Trans. Algorithms 12, No. 2, Article No. 21, 41 p. (2016; Zbl 1398.68245)] guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [LIPIcs – Leibniz Int. Proc. Inform. 25, 312–324 (2014; Zbl 1359.68132); SIAM J. Discrete Math. 29, No. 4, 1864–1894 (2015; Zbl 1323.05119)] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices. In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. \(\mathcal{F}\)-Packing is a typical example: for a family \(\mathcal{F}\) of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph \(G\) contains \(k\) vertex-disjoint subgraphs such that each of them contains a graph in \(\mathcal{F}\) as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of \(\mathcal{F}\)-Packing: for an integer \(\ell \geqslant 1\), one aims at finding either minor-models that are pairwise at distance at least \(\ell\) in \(G\) (\(\ell\)-\(\mathcal{F}\)-Packing), or such that each vertex in \(G\) belongs to at most \(\ell \) minors-models (\(\mathcal{F}\)-Packing with \(\ell\)-Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C83 | Graph minors |
| 90C27 | Combinatorial optimization |
Keywords:
parameterized complexity; linear kernels; packing problems; dynamic programming; protrusion replacement; graph minorsReferences:
| [1] | Abrahamson, K.R., Fellows, M.R.: Finite automata, bounded treewidth, and well-quasiordering. In: Proceedings of Graph Structure Theory, Contemporary Mathematics, vol. 147, pp. 539-564. American Mathematical Society (1991) · Zbl 0791.05094 |
| [2] | Adler, I., Dorn, F., Fomin, F.V., Sau, I., Thilikos, D.M.: Faster parameterized algorithms for minor containment. Theor. Comput. Sci. 412(50), 7018-7028 (2011) · Zbl 1228.68035 · doi:10.1016/j.tcs.2011.09.015 |
| [3] | Adler, I., Kolliopoulos, S.G., Krause, P.K., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Irrelevant vertices for the planar disjoint paths problem. J. Comb. Theory Ser. B 122, 815-843 (2017) · Zbl 1350.05068 · doi:10.1016/j.jctb.2016.10.001 |
| [4] | Alber, J., Fellows, M., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM 51(3), 363-384 (2004) · Zbl 1192.68337 · doi:10.1145/990308.990309 |
| [5] | Arnborg, S., Courcelle, B., Proskurowski, A., Seese, D.: An algebraic theory of graph reduction. J. ACM 40(5), 1134-1164 (1993) · Zbl 0795.68156 · doi:10.1145/174147.169807 |
| [6] | Atminas, A., Kaminski, M., Raymond, J.-F.: Scattered packings of cycles. Theor. Comput. Sci. 647, 33-42 (2016) · Zbl 1351.68111 · doi:10.1016/j.tcs.2016.07.021 |
| [7] | Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305-1317 (1996) · Zbl 0864.68074 · doi:10.1137/S0097539793251219 |
| [8] | Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (meta) kernelization. J. ACM 63(5), 44:1-44:69 (2016) · Zbl 1425.68137 · doi:10.1145/2973749 |
| [9] | Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570-4578 (2011) · Zbl 1221.68099 · doi:10.1016/j.tcs.2011.04.039 |
| [10] | Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Inf. Comput. 167(2), 86-119 (2001) · Zbl 1008.05140 · doi:10.1006/inco.2000.2958 |
| [11] | Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algo- rithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 555-581 (1992) · Zbl 0753.05062 · doi:10.1007/BF01758777 |
| [12] | Büchi, J.R.: Weak second order arithmetic and finite automata. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 6, 66-92 (1960) · Zbl 0103.24705 · doi:10.1002/malq.19600060105 |
| [13] | Chekuri, C., Chuzhoy, J.: Large-treewidth graph decompositions and applications. In: Proceedings of the 45th Symposium on the Theory of Computing (STOC), pp. 291-300 (2013) · Zbl 1293.05040 |
| [14] | Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. In: Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC), pp. 60-69 (2014) · Zbl 1315.05131 |
| [15] | 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 |
| [16] | Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015) · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [17] | 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. In: Proceedings of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 150-159. IEEE Computer Society (2011) · Zbl 1292.68122 |
| [18] | Demaine, E.D., Hajiaghayi, M.: Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28(1), 19-36 (2008) · Zbl 1174.05115 · doi:10.1007/s00493-008-2140-4 |
| [19] | Diestel, R.: Graph Theory, vol. 173, 4th edn. Springer, Berlin (2010) · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6 |
| [20] | Erdős, P., Pósa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347-352 (1965) · Zbl 0129.39904 · doi:10.4153/CJM-1965-035-8 |
| [21] | Fellows, M.R., Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Graph-based data clustering with overlaps. Discrete Optim. 8(1), 2-17 (2011) · Zbl 1248.90070 · doi:10.1016/j.disopt.2010.09.006 |
| [22] | Fellows, M.R., Langston, M.A.: An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations (extended abstract). In: Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 520-525 (1989) |
| [23] | Fellows, M.R., Langston, M.A.: On search, decision, and the efficiency of polynomial-time algorithms. J. Comput. Syst. Sci. 49(3), 769-779 (1994) · Zbl 0938.68599 · doi:10.1016/S0022-0000(05)80079-0 |
| [24] | Fernau, H., López-Ortiz, A., Romero, J.: Kernelization algorithms for packing problems allowing overlaps. In: Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation, (TAMC), volume 9076 of LNCS, pp. 415-427 (2015) · Zbl 1460.68074 |
| [25] | Fomin, F.V., Golovach, P.A., Thilikos, D.M.: Contraction obstructions for treewidth. J. Comb. Theory Ser. B 101(5), 302-314 (2011) · Zbl 1223.05022 · doi:10.1016/j.jctb.2011.02.008 |
| [26] | Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 748-759 (2011) · Zbl 1377.68324 |
| [27] | Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 503-510 (2010) · Zbl 1288.68116 |
| [28] | Fomin, F.V., Saurabh, S., Thilikos, D.M.: Strengthening Erdős-Pósa property for minor-closed graph classes. J. Gr. Theory 66(3), 235-240 (2011) · Zbl 1216.05148 · doi:10.1002/jgt.20503 |
| [29] | Garnero, V., Paul, C., Sau, I., Thilikos, D.M.: Explicit linear kernels via dynamic programming. SIAM J. Discrete Math. 29(4), 1864-1894 (2015) · Zbl 1323.05119 · doi:10.1137/140968975 |
| [30] | Giannopoulou, A.: Partial Orderings and Algorithms on Graphs. PhD thesis, Department of Mathematics, University of Athens, Greece (2012) |
| [31] | Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), volume 4596 of LNCS, pp. 375-386 (2007) · Zbl 1171.68488 |
| [32] | Jim Geelen, J., Huynh, T., Richter, R.B.: Explicit bounds for graph minors. CoRR (2013). arXiv:1305.1451 · Zbl 1391.05243 |
| [33] | Kawarabayashi, K., Kobayashi, Y.: Linear min – max relation between the treewidth of \[HH\]-minor-free graphs and its largest grid. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 14 of LIPIcs, pp. 278-289 (2012) · Zbl 1244.05212 |
| [34] | Kawarabayashi, K., Wollan, P.: A simpler algorithm and shorter proof for the graph minor decomposition. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 451-458 (2011) · Zbl 1288.05257 |
| [35] | 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), 21 (2016) · Zbl 1398.68245 |
| [36] | Kloks, T.: Treewidth. Computations and Approximations. Springer, Berlin (1994) · Zbl 0825.68144 |
| [37] | Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41-72 (2011) · Zbl 1258.68068 |
| [38] | Mazoit, F.: A single exponential bound for the redundant vertex theorem on surfaces. CoRR (2013). arXiv:1309.7820 |
| [39] | Moser, H.: A problem kernelization for graph packing. In: Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 5404 of LNCS, pp. 401-412 (2009) · Zbl 1206.68239 |
| [40] | Robertson, N., Seymour, P.D.: Graph minors. V. Excluding a planar graph. J. Comb. Theory Ser. B 41(1), 92-114 (1986) · Zbl 0598.05055 · doi:10.1016/0095-8956(86)90030-4 |
| [41] | Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65-110 (1995) · Zbl 0823.05038 · doi:10.1006/jctb.1995.1006 |
| [42] | Robertson, N., Seymour, P.D.: Graph minors. XVI. excluding a non-planar graph. J. Comb. Theory Ser. B 89(1), 43-76 (2003) · Zbl 1023.05040 · doi:10.1016/S0095-8956(03)00042-X |
| [43] | Romero, J., López-Ortiz, A.: The \[{\cal{G}}\] G-packing with \[t\] t-overlap problem. In: Proceedings of the 8th International Workshop on Algorithms and Computation (WALCOM), volume 8344 of LNCS, pp. 114-124 (2014) · Zbl 1408.68080 |
| [44] | Romero, J., López-Ortiz, A.: A parameterized algorithm for packing overlapping subgraphs. In: Proceedings of the 9th International Computer Science Symposium in Russia (CSR), volume 8476 of LNCS, pp. 325-336 (2014) · Zbl 1407.68372 |
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.
