Abstract
We study (vertex-disjoint) packings of paths of length two (i.e., of P 2’s) in graphs under a parameterized perspective. Starting from a maximal P 2-packing ℘ of size j we use extremal combinatorial arguments for determining how many vertices of ℘ appear in some P 2-packing of size (j+1) (if such a packing exists). We prove that one can ‘reuse’ 2.5j vertices. We also show that this bound is asymptotically sharp. Based on a WIN-WIN approach, we build an algorithm which decides, given a graph, if a P 2-packing of size at least k exists in time \(\mathcal{O}^{*}(2.448^{3k})\) .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bazgan C, Hassin R, Monnot J (2005) Approximation algorithms for some vehicle routing problems. Discrete Appl Math 146:27–42
De Bontridder KMJ, Halldórsson BV, Halldórsson MM, Lenstra JK, Ravi R, Stougie L (2003) Approximation algorithms for the test cover problem. Math Program, Ser B 98:477–491
Chen J, Fernau H, Kanj YA, Xia G (2007) Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J Comput 37:1077–1108
Chen J, Fernau H, Ning D, Raible D, Wang J (2008) A parameterized perspective on P2-packings. Technical report 0804.0570, ArXiv, http://arxiv.org/abs/0804.0570
Cotta C, Moscato P (2002) On the parameterized complexity of problems related with feature identification for gene expression data mining techniques. Bioinformatics 1:1–8
Cotta C, Moscato P (2003) The k-feature set problem is W[2]-complete. J Comput Syst Sci 67:686–690
Dehne F, Fellows M, Fernau H, Prieto E, Rosamond F (2006) Nonblocker: parameterized algorithmics for minimum dominating set. In: Štuller J, Wiedermann J, Tel G, Pokorný J, Bielikova M (eds) Software seminar SOFSEM. LNCS, vol 3831. Springer, Berlin, pp 237–245
Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin
Estivill-Castro V, Fellows MR, Langston MA, Rosamond FA (2005) FPT is P-time extremal structure I. In: Broersma H, Johnson M, Szeider S (eds) Algorithms and complexity in Durham ACiD 2005. Texts in algorithmics, vol 4. King’s College, London, pp 1–41
Fellows M (2002) Parameterized complexity: the main ideas and connections to practical computing. Electron Notes Theor Comput Sci 61
Fernau H (2005) Parameterized algorithmics: a graph-theoretic approach. Habilitationsschrift, Universität Tübingen, Germany
Fernau H, Manlove DF (2006) Vertex and edge covers with clustering properties: Complexity and algorithms. In: Algorithms and complexity in Durham ACiD 2006. King’s College, London, pp 69–84
Fernau H, Raible D (2008) A parameterized perspective on packing paths of length two. In: Yang B, Du D-Z, An Wang C (eds) Combinatorial optimization and applications COCOA. LNCS, vol 5165. Springer, Berlin, pp 54–63
Gallai T (1959) Über extreme Punkt-und Kantenmengen. Ann Univ Sci Bp Eötvös Sect Math 2:133–138
Hassin R, Rubinstein S (1997) An approximation algorithm for maximum packing of 3-edge paths. Inf Process Lett 63:63–67
Hassin R, Rubinstein S (2006) An approximation algorithm for maximum triangle packing. Discrete Appl Math 154:971–979; 2620 [Erratum]
Hell P, Kirkpatrick DG (1982) Star factors and star packings. Technical report 82-6, Computing Science, Simon Fraser University, Burnaby, BC V5A1S6, Canada
Hopcroft JE, Karp RM (1973) An n 5/2-algorithm for maximum matchings in bipartite graphs. SIAM J Comput 2(4):225–231
Khot S, Raman V (2002) Parameterized complexity of finding subgraphs with hereditary properties. Theor Comput Sci 289:997–1008
Kirkpatrick DG, Hell P (1978) On the completeness of a generalized matching problem. In: ACM symposium on theory of computing STOC, pp. 240–245
Kosowski A, Małafiejski M, Żyliński P (2005) Packing three-vertex paths in a subcubic graph. In: Felsner S (ed) 2005 European conference on combinatorics, graph theory and applications (EuroComb ’05). DMTCS proceedings, Discrete mathematics and theoretical computer science, vol AE. Springer, Berlin, pp 213–218
Koutis I (2008) Faster algebraic algorithms for path and packing problems. In: Aceto L, Damgård I, Ann Goldberg L, Halldórsson MM, Ingólfsdóttir A, Walukiewicz I (eds) Automata, languages and programming, 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I: Tack A: algorithms, automata, complexity, and games. Lecture notes in computer science, vol 5125. Springer, Berlin, pp 575–586
Liu Y, Lu S, Chen J, Sze S-H (2006) Greedy localization and color-coding: improved matching and packing algorithms. In: Bodlaender HL, Langston M (eds) International workshop on parameterized and exact computation IWPEC. LNCS, vol 4169. Springer, Berlin, pp 84–95
Micali S, Vazirani VV (1980) An \(\mathcal{O}(\sqrt{|V|}|E|)\) algorithm for finding maximum matchings in general graphs. In: Symposium on foundations of computer science. IEEE Press, New York, pp 17–27
Monnot J, Toulouse S (2007) The P k partitioning problem and related problems in bipartite graphs. In: van Leeuwen J (eds) Software seminar SOFSEM 2008. Lecture notes in computer science, vol 4362. Springer, Berlin, pp 422–433
Moser H (2009) A problem kernelization for graph packing. In: Nielsen M (eds) Software seminar SOFSEM. LNCS, vol 5404. Springer, Berlin, pp 401–412
Plesník J (1984) Equivalence between the minimum covering problem and the maximum matching problem. Discrete Math 49:315–317
Prieto E, Sloper C (2003) Either/or: Using vertex cover structure in designing FPT-algorithms—the case of k-internal spanning tree. In: Proceedings of WADS 2003, workshop on algorithms and data structures. LNCS, vol 2748. Springer, Berlin, pp 465–483
Prieto E, Sloper C (2004) Looking at the stars. In: Downey R, Fellows M, Dehne F (eds) International workshop on parameterized and exact computation IWPEC 2004. LNCS, vol 3162. Springer, Berlin, pp 138–148
Wang J, Feng Q (2008) An O *(3.523k) parameterized algorithm for 3-set packing. In: Agrawal M (eds) Theory and applications of models of computation TAMC. LNCS, vol 4978. Springer, Berlin, pp 82–93
Wang J, Ning D, Feng Q, Chen J (2008) An improved parameterized algorithm for a generalized matching problem. In: Agrawal M (eds) Theory and applications of models of computation TAMC. LNCS, vol 4978. Springer, Berlin, pp 212–222
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fernau, H., Raible, D. A parameterized perspective on packing paths of length two. J Comb Optim 18, 319–341 (2009). https://doi.org/10.1007/s10878-009-9230-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-009-9230-0