Abstract
We study the parameterized complexity of two graph packing problems, Edge-Disjoint \(k\)-Packing of \(s\)-Stars and Edge-Disjoint \(k\)-Packing of \(s\)-Cycles. With respect to the choice of parameters, we show that although the two problems are FPT with both k and s as parameters, they are unlikely to be fixed-parameter tractable when parameterized by only k or only s. In terms of kernelization complexity, we show that Edge-Disjoint \(k\)-Packing of \(s\)-Stars has a kernel with size polynomial in both k and s, but in contrast, unless NP \(\subseteq \) coNP/poly, Edge-Disjoint \(k\)-Packing of \(s\)-Cycles does not have a kernel with size polynomial in both k and s, and moreover does not have a kernel with size polynomial in s for any fixed k. Specifically, (1) from the negative direction, we show that Edge-Disjoint \(k\)-Packing of \(s\)-Stars is W[1]-hard with parameter k in general graphs, and that Edge-Disjoint \(k\)-Packing of \(s\)-Cycles is W[1]-hard with parameter k and NP-hard for any even \(s \ge 4\) in bipartite graphs; (2) from the positive direction, we show that Edge-Disjoint \(k\)-Packing of \(s\)-Stars admits a \(ks^2\) kernel, and that Edge-Disjoint \(k\)-Packing of 4-Cycles admits a \(96k^2\) kernel in general graphs and a 96k kernel in planar graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For the general problem of deciding whether a graph G contains k edge-disjoint copies of a graph H, the running time of this algorithm [5, Corollary 5.7] is \(4^{rk + O(\log ^3(rk))} n^{r+1}\), where n and r are the numbers of vertices in G and H, respectively. The \(n^{r+1}\) factor in the running time accounts for the time for solving the subproblem of determining whether G contains H as a subgraph, by brute force. The brute-force algorithm for this subproblem can be replaced by faster algorithms in our setting, with polynomial running time when H is an s-star, or \(2^{O(s)}\mathrm {poly}(n)\) time when H is an s-cycle [1].
- 2.
We remark that in our setting of Edge-Disjoint \(k\)-Packing of \(s\)-Cycles, since any two different s-cycles share at most \(s-2\) edges, the base case of \(f(0,k) = 1\) in the analysis of [13, page 170] can be upgraded to \(f(1,k) = 1\), which saves 1 in the exponent and yields an \(O(k^{s-1})\) kernel.
- 3.
We remark that the construction in our proof of Theorem 2 can be easily adapted to prove the hardness of all four variants of related problems on vertex/edge-disjoint cycles/paths.
References
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)
Bafna, V., Pevzner, P.A.: Genome rearrangements and sorting by reversals. SIAM J. Comput. 25(2), 272–289 (1996)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277–305 (2014)
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)
Chen, J., Kneis, J., Lu, S., Molle, D., Richter, S., Rossmanith, P., Sze, S., Zhang, F.: Randomized divide-and-conquer: improved path, matching, and packing algorithms. SIAM J. Comput. 38(6), 2526–2547 (2009)
Colbourn, C.J.: The Combinatorics of Network Reliability. Oxford University Press Inc., New York (1987)
Colbourn, C.J.: Edge-packings of graphs and network reliability. Discrete Math. 72, 49–61 (1988)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
Dyer, M.E., Frieze, A.M.: On the complexity of partitioning graphs into connected subgraphs. Discrete Appl. Math. 10(2), 139–153 (1985)
Feder, T., Subi, C.S.: Packing edge-disjoint triangles in given graphs. Electron. Colloquium Comput. Complex. (ECCC) 19, 13 (2012)
Fellows, M.R., Guo, J., Moser, H., Niedermeier, R.: A generalization of Nemhauser and Trotter’s local optimization theorem. J. Comput. Syst. Sci. 77(6), 1141–1158 (2011)
Fellows, M.R., Heggernes, P., Rosamond, F.A., Sloper, C., Telle, J.A.: Finding \(k\) disjoint triangles in an arbitrary graph. In: Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 235–244 (2004)
Fellows, M.R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D.M., Whitesides, S.: Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica 52(2), 167–176 (2008)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)
Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 375–386. Springer, Heidelberg (2007)
Heath, L.S., Vergara, J.P.C.: Edge-packing in planar graphs. Theor. Comput. Syst. 31, 629–662 (1998)
Holyer, I.: The NP-completeness of some edge-partition problems. SIAM J. Comput. 10(4), 713–717 (1981)
Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79, 39–49 (2013)
Masuyama, S., Ibaraki, T.: Chain packing in graphs. Algorithmica 6, 826–839 (1991)
Mathieson, L., Prieto, E., Shaw, P.: Packing edge disjoint triangles: a parameterized view. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 127–137. Springer, Heidelberg (2004)
Moser, H.: A problem kernelization for graph packing. In 35th International Conference on Current Trends in Theory and Practice of Computer Science, pp. 401–412 (2009)
Prieto, E., Sloper, C.: Looking at the stars. Theor. Comput. Sci. 351(3), 437–445 (2006)
Wang, J., Ning, D., Feng, Q., Chen, J.: An improved parameterized algorithm for a generalized matching problem. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 212–222. Springer, Heidelberg (2008)
Yang, Y.: Towards optimal kernel for edge-disjoint triangle packing. Inf. Process. Lett. 114(7), 344–348 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Jiang, M., Xia, G., Zhang, Y. (2015). Edge-Disjoint Packing of Stars and Cycles. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science(), vol 9486. Springer, Cham. https://doi.org/10.1007/978-3-319-26626-8_49
Download citation
DOI: https://doi.org/10.1007/978-3-319-26626-8_49
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26625-1
Online ISBN: 978-3-319-26626-8
eBook Packages: Computer ScienceComputer Science (R0)