×

Packing paths in digraphs. (English) Zbl 1033.05079

Let \(\mathcal G\) be a fixed family of directed graphs. A \(\mathcal G\)-packing of a digraph \(H\) is a collection of vertex-disjoint subgraphs of \(H\), each isomorphic to a member of \(\mathcal G\). A \(\mathcal G\)-packing problem is a problem to decide if an instance graph \(H\) has a \(\mathcal G\)-packing that covers at least \(k\) vertices of \(H\) (where \(k\) is a part of the instance). Denote by \(\vec{P}_m\) a directed path of length \(m\). The authors prove that the \(\mathcal G\)-packing problem is NP-complete for a family of directed paths \({\mathcal G}\subseteq \{\vec{P}_1,\vec{P}_2,\vec{P}_3,\ldots\}\) unless \(\mathcal G\) satisfies one of the conditions: (i) \(\vec{P}_1 \in {\mathcal G}\) and each member of \(\mathcal G\) has an odd length, or (ii) \(\vec{P}_1,\vec{P}_2 \in {\mathcal G}\). When \(\mathcal G\) satisfies (i) or (ii), the \(\mathcal G\)-packing problem is polynomial time solvable. In case (ii) (which is more interesting than case (i)) the authors prove a Berge type augmentation configuration theorem and a min-max characterization. They also construct a polynomial time algorithm solving the \(\mathcal G\)-packing problem in this case.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and Path factors of a graph, In: and Graphs and applications (Editors), John Wiley & Sons, New York, 1985, 1-21.
[2] Brewster, Info Process Lett 86 pp 101– (2003)
[3] and Digraph packings with stars, submitted.
[4] and Sidepath results on packing P1’s and P1’s, Technical report, http://eprints.biblio.unitn.it/archive/00000352/
[5] Cornuéjols, Oper Res Lett 1 pp 139– (1982)
[6] Goldberg, SIAM J Discrete Math 12 pp 1– (1999)
[7] Edmonds, Can J Math 17 pp 449– (1965) · Zbl 0132.20903
[8] Hell, Infor Process Lett 12 pp 33– (1981)
[9] Hell, Discrete Math 49 pp 45– (1984)
[10] Hell, Electron Notes Discrete Math 5 (2000)
[11] Hopcroft, SIAM J Comput 2 pp 255– (1973)
[12] Lichtenstein, SIAM J on Computing 11 pp 2– (1982)
[13] and Matching theory, North-Holland, Amsterdam, 1986.
[14] Loebl, J Combin Theory Ser B 59 pp 106– (1993)
[15] Graph packing problems, M.Sc. Thesis, Simon Fraser University, 1998.
[16] Data structures and network algorithms, Soc Ind Appl Math, 1983. · Zbl 0584.68077
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.