×

zbMATH — the first resource for mathematics

On packing shortest cycles in graphs. (English) Zbl 1197.05119
Summary: We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth \(g\) (\(g\)-ESCP) and its vertex-disjoint analogue \(g\)-VSCP. In the case \(g=3\), A. Caprara and R. Rizzi [“Packing triangles in bounded degree graphs”, Inf. Process. Lett. 84, No. 4, 175–180 (2002; Zbl 1042.68087)] have shown that \(g\)-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while \(g\)-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For \(g \in \{4,5\}\), we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each \(g \geqslant 6\), both problems are APX-hard already for graphs with maximum degree 3.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
68W25 Approximation algorithms
PDF BibTeX Cite
Full Text: DOI
References:
[1] Berman, P.; Karpinski, M., On some tighter inapproximability results (1998), (), 200-209
[2] Caprara, A.; Rizzi, R., Packing triangles in bounded degree graphs (2001), Information processing letters, 84, 4, 175-180, (2002) · Zbl 1042.68087
[3] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of incompleteness, (1979), Freeman San Francisco · Zbl 0411.68039
[4] Holyer, I., The NP-completeness of some edge-partition problems, SIAM journal of computing, 10, 4, 713-717, (1981) · Zbl 0468.68069
[5] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[6] Minty, G.J., On maximal independent sets of vertices in claw-free graphs, Journal of combinatorial theory series B, 28, 284-304, (1980) · Zbl 0434.05043
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.