On packing shortest cycles in graphs.

*(English)*Zbl 1197.05119Summary: 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 |

##### Keywords:

algorithms; approximation algorithms; combinatorial problems; graph algorithms; shortest cycles; packing; complexity
PDF
BibTeX
Cite

\textit{D. Rautenbach} and \textit{F. Regen}, Inf. Process. Lett. 109, No. 14, 816--821 (2009; Zbl 1197.05119)

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.