Packing cycles in undirected graphs

doi:10.1016/S0196-6774(03)00052-X

Journal of Algorithms

Volume 48, Issue 1, August 2003, Pages 239-256

https://doi.org/10.1016/S0196-6774(03)00052-X Get rights and content

Abstract

Given an undirected graph G with n nodes and m edges, we address the problem of finding a largest collection of edge-disjoint cycles in G. The problem, dubbed Cycle Packing, is very closely related to a few genome rearrangement problems in computational biology. In this paper, we study the complexity and approximability of Cycle Packing, about which very little is known although the problem is natural and has practical applications. We show that the problem is $APX$ -hard but can be approximated within a factor of O(logn) by a simple greedy approach. We do not know whether the O(logn) factor is tight, but we give a nontrivial example for which the ratio achieved by greedy is not constant, namely $Ω(log n/(loglog n))$ . We also show that, for “not too sparse” graphs, i.e., graphs for which $m=Ω(n^{1+1/t+δ})$ for some positive integer t and for any fixed δ>0, we can achieve an approximation arbitrarily close to 2t/3 in polynomial time. In particular, for any ε>0, this yields a 4/3+ε approximation when $m=Ω(n^{3/2+δ})$ , therefore also for dense graphs. Finally, we briefly discuss a natural linear programming relaxation for the problem.

References (11)

G. Ausiello et al.
Combinatorial Optimization Problems and their Approximability Properties
(1999)
V. Bafna et al.
Genome rearrangements and sorting by reversals
SIAM J. Comput.
(1996)
P. Berman et al.
On some tighter inapproximability results
B. Bollobás
Extremal Graph Theory
(1978)
A. Caprara
Sorting Permutations by reversals and Eulerian cycle decompositions
SIAM J. Discrete Math.
(1999)

There are more references available in the full text version of this article.

Cited by (50)

Tree Derived Architectures with Decycling Number Equal to Cycle Packing Number
2015, Procedia Computer Science
Covering vertices by a specified number of disjoint cycles, edges and isolated vertices
2013, Discrete Mathematics
Citation Excerpt :
There is a large amount of literature concerning conditions in terms of, for instance, order, size, vertex degrees, degree sums, independence number, and feedback vertex sets that are sufficient for the existence of some number of vertex-disjoint cycles which may have further restrictive conditions (see e.g. [5–7,9,8,13,18]). The algorithmic problems concerning cycle packings are usually hard, and so approximation algorithms were described (see e.g. [4,11,17,19]). Also, several researchers mention practical applications in computational biology such as reconstruction of evolutionary trees or genomic analysis.
Let $n, k$ be integers with $n \geq k \geq 2$ , and let $G$ be a graph of order $n$ and $S$ be a subset of $V (G)$ . We define $μ (S) : = min {max {d_{G} (x), d_{G} (y)} ∣ x, y \in S, x \neq y, x y \notin E (G)}$ if there exist two nonadjacent vertices in $S$ ; otherwise $μ (S) : = + \infty$ .
Fujita [S. Fujita, Degree conditions for the partition of a graph into cycles, edges and isolated vertices, Discrete Math. 309 (2009) 3534–3540] proved that if $μ (V (G)) \geq (n - k + 1) / 2$ , then $G$ contains $k$ vertex-disjoint subgraphs $H_{1}, \dots, H_{k}$ such that $⋃_{i = 1}^{k} V (H_{i}) = V (G)$ and each $H_{i}$ is a cycle or $K_{2}$ or $K_{1}$ unless $G$ is an exceptional graph. In this paper, we generalize this result as follows: if $μ (S) \geq (n - k + 1) / 2$ , then $G$ contains $k$ vertex-disjoint subgraphs $H_{1}, \dots, H_{k}$ such that $S \subseteq ⋃_{i = 1}^{k} V (H_{i})$ and each $H_{i}$ is a cycle or $K_{2}$ or $K_{1}$ unless $G$ is an exceptional graph.
Performance and design of cycles in consensus networks
2013, Systems and Control Letters
This work explores the role of cycles in consensus seeking networks for analysis and synthesis purposes. Cycles are critical for many reasons including improving the convergence rate of the system, resilience to link failures, and the overall performance of the system. The focus of this work examines how cycles impact the $H_{2}$ performance of consensus networks. A first contribution shows that the addition of cycles always improves the performance of the system. We provide an analytic characterization of how the addition of edges improves the performance, and show that it is related to the inverse of the cycle lengths and the number of shared edges between independent cycles. These results are then used to consider the design of consensus networks. In this direction we present an $ℓ_{1}$ -relaxation method that leads to a convex program for adding a fixed number of edges to a consensus networks. We also demonstrate how this relaxation can be used to embed additional performance criteria, such as maximization of the algebraic connectivity of the graph.
Disjoint cycles intersecting a set of vertices
2012, Journal of Combinatorial Theory. Series B
A classic theorem of Erdős and Pósa states that there exists a constant c such that for all positive integers k and graphs G, either G contains k vertex disjoint cycles, or there exists a subset of at most $c k \log k$ vertices intersecting every cycle of G. We consider the following generalization of the problem: fix a subset S of vertices of G. An S-cycle is a cycle containing at least one vertex of S. We show that again there exists a constant $c^{'}$ such that G either contains k disjoint S-cycles, or there exists a set of at most $c^{'} k \log k$ vertices intersecting every S-cycle. The proof yields an algorithm for finding either the disjoint S-cycles or the set of vertices intersecting every S-cycle. An immediate consequence is an $O (\log n)$ -approximation algorithm for finding disjoint S-cycles.
Packing cycles through prescribed vertices under modularity constraints
2012, Advances in Applied Mathematics
The well-known theorem of Erdős–Pósa says that either a graph G has k disjoint cycles or there is a vertex set X of order at most $f (k)$ for some function f such that $G ∖ X$ is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization.
In this paper, we present a common generalization of the following Erdős–Pósa properties:
- 1.
  The Erdős–Pósa property for cycles of length divisible by a fixed integer p (Thomassen, 1988 [19]).
- 2.
  The Erdős–Pósa property for S-cycles, i.e., cycles which contain a vertex of a prescribed vertex set S (Kakimura, Kawarabayashi, and Marx, 2011 [10] and Pontecorvi and Wollan, 2010 [13]).
Namely, given integers $k, p$ , and a vertex set S (whose size may not depend on k and p), we prove that either a graph G has k disjoint S-cycles, each of which has length divisible by p, or G has a vertex set X of order at most $f (k, p)$ such that $G ∖ X$ has no such a cycle.
Induced packing of odd cycles in planar graphs
2012, Theoretical Computer Science
An induced packing of odd cycles in a graph is a packing such that there is no edge in the graph between any two odd cycles in the packing. We prove that an induced packing of $k$ odd cycles in an $n$ -vertex graph can be found (if it exists) in time $2^{O (k^{3 / 2})} \cdot n^{2 + ϵ}$ (for any constant $ϵ > 0$ ) when the input graph is planar. We also show that deciding if a graph has an induced packing of two odd induced cycles is NP-complete.

View all citing articles on Scopus

¹: Basic Research in Computer Science, Centre of the Danish National Research Foundation.

View full text

Packing cycles in undirected graphs

Abstract

Combinatorial Optimization Problems and their Approximability Properties

Genome rearrangements and sorting by reversals

SIAM J. Comput.

On some tighter inapproximability results

Extremal Graph Theory

Sorting Permutations by reversals and Eulerian cycle decompositions

SIAM J. Discrete Math.