. Obviously,
. Then
..
Now, let 
and let us assume that for all even graphs G such that 
the strict inequalities 
hold.
Let G be an even graph such that
. We will show 
for all
.
Let 
such that
. Consider the graphs 
and
. 
is even and
. Obviously, 
and
. But also 
must hold, otherwise 
would not be a minimizer of L on
.
Hence,
. Applying the induction assumption to
, we then get:
Here 
is a minimizer of L on
. From this we finally conclude 
By
, we denote the family of all cycle packings of G. We get
Theorem 1. Let G be even,
. Every cycle packing 
that minimizes L on 
is maximum, i.e.
.
Proof. Let 
be a minimizer of L on
. We can assume that 
We will show that
.
For this, consider the non-even graph 
obtained by adding a component 
and an additional edge to G. Obviously, 
is even and
. For the packing 
with 
it holds 
and
. We will show 
.
For an arbitrary packing
, the remainder 
is the dis- joint union of 
and some even graph H that contains at least one cycle 
of length
. Let
.
If the component 
is not contained in H, then 
is one of the cycles
, i.e.
. In this case C is a cycle in G.
Consider the packing 
Then 
. We get
i.e. 
We conclude, that there must be a minimizer 
of L on
, such that
. Obviously, 
, i.e. 
with
.
We get
Applying Lemma 1 to the even graph
, we get for
:
where the last inequality is strict if
.
Now, let 
be a maximum cycle packing that mini-
mizes L on
, i.e.
.
Then 
with 
minimizes L on
. Obviously,
. We get
where the inequality is strict, if
.
It follows
. But 
was a minimizer on
, i.e.
. Therefore, 
and
. 
A maximum cycle packing 
of G is said to be max-min if it minimizes L on
. The quantity 
is the max-min cycle value of G. The determination of a max-min cycle packing 
will be called the max-min cycles packing problem (mmcp-problem) of G. Clearly, max-min cycle packings, in general, are not unique.
The following theorem relates the determination of 
to the determination of the max-min cycle values for even subgraphs
.
Theorem 2. Let G be even. Then
Proof. Let 
be an even subgraph of G and 
be max-min.
A packing 
then induces a
packing
. We then get
and conclude
Now, let 
be max-min and let 
and 
be induced by 
and
, respectively.
The packings 
and 
must also be max-min. We get
The proof of Theorem 2 immediately induces
Corollary 1.
1)
, for every even subgraph H of G.
2)
.
3. A Shortest Path Approach for the MMCP-Problem
Theorem 2 gives reason to treat the mmcp-problem as a shortest path problem within a suitable weighted acyclic network 
3.1. The MMCP-Network 
Let the edges in E be labelled, i.e.
. In a canonical way, a subgraph 
is determined by its 
incidence vector
i.e.,
Let 
and
.
1For 
we will use “nodes”, in G we use “vertices”.
We will identify the set X of nodes1 in 
with the set of even subgraphs of G. Each node 
corresponds to some specific even subgraph H of G (we will write
). Nodes in 
are also assigned to stages
, i.e. 
.
For the construction of
, the nodes and edges are defined inductively:
・ The unique node in 
corresponds to the subgraph 
of G with empty edge set. Assume that the set of nodes 
is given. Then a node belongs to 
if there is 
such that
We call 
to be a successor of
. The set of all successors of 
is called an expansion of
, and a specific successor 
is generated by expanding
.
・ An edge in U corresponds to some specific cycle in G. Edges exist only between nodes at consecutive stages. An edge 
if and only if for the cor- responding subgraphs 
is a successor of
.
・ As edge weights we set
.
Clearly, 
is acyclic and the number of stages in 
cannot exceed
. An even subgraph 
is reachable in 
if there is a path 
with starting node 
and end node H. In a canonical way, any path 
induces a cycle packing
. The set 
describes the cycles used in the successive expansions of the corresponding nodes.
Obviously, G is reachable in
, but not all even subgraphs of G have this property. Hence, not every cycle packing 
is induced by some paths
. We get
Lemma 2. Let 
be reachable in 
and 
be a cycle-packing of H of cardinality s. Then there is a path 
in 
that induces
.
Proof. Let 
be a cycle packing of H of cardinality
. Without loss of generality, we can assume that the cycles in 
are ordered such that
. Let 
and 
be the even subgraph of H induced by
. Since the cycles are mutually edge-disjoint, the number 
coincides with
. Therefore, 
is generated by an expansion of
, i.e. there is a path 
that induces
. Moreover, if 
and 
are two different cycle-packings of H, then the corresponding paths in 
must be different. 
Together with Theorem 1, we conclude for the special case
:
Proposition 3. 
is a max-min cycle packing of G if and only if 
corresponds to a shortest path 
in
.
In order to reduce the number of graphs that have to be expanded within the algorithmic procedure, those subgraphs H in 
have to be identified that cannot be contained in
. Such an identification, preferably, should be done as early as possible in the calculations. The following proposition gives conditions for such a situation. They can be checked during the shortest path procedure. If such a condition is satisfied, H must never be expanded.
Proposition 4. Let 
be a shortest path in 
and let 
be reachable. If
1) 
or
2) 
holds, then 
Proof. Since
, 
holds. Assume that
. Then there is a cycle packing 
induced by
. The packing
, therefore, must be max-min. Hence,
. This leads to the contradiction. 
3.2. An A*-Shortest Path Algorithm
For an even subgraph
, let 
denote the length of the shortest cycle in H, then,
is a lower bound for the max-min cycle value
. Moreover, the function 
is a monotonous node potential on 
in the following sense
Lemma 3. For
, let 
be two even subgraphs of G adjacent in 
such that
. Then
Proof. Let 
and 
be the lengths of the shortest cycles in 
and
, respectively. Then
The last inequality is true, since
. Hence,
In [14] , it is described how information of a monotonous node potential could be incorporated into a searching strategy for the shortest path procedure. Such an 
- search algorithm constructs 
successively and expands only such nodes that are candidates for a shortest path
.
The 
procedure essentially manages two sets of nodes in 
and updates several quantities:
・ X: even subgraphs of G that are candidates to determine
.2
・ L: subgraphs that are already expanded. For
, a shortest path 
is already constructed.
・ 
: index of the stage in 
at which H is considered
. If 
terminates, 
is the cardinality of a maximum cycle packing.
・ 
: (currently) the shortest length of a path
. If
, then
. If 
stops,
.
・ 
: monotonous node potential.
The scheme of such an 
-search is outlined as follows.
The determination of 
in step 1 requires the determination of the girth of
. This can efficiently be done by the shortest paths procedures. For the expansion of H in step 2, the value 
and the set C of all cycles in 
that contain 
must be generated. This makes it necessary to identify all simple paths between u and v in the graph
. Typically, this subproblem is attacked by using DFS procedures. In general, it is NP-hard ( [15] ).
Step 3 incorporates the stopping rule (
) and the elimination of super- fluous nodes (and sub-paths) according to Prop. 4.
Coming from step 2, 
terminates in step 3 if G is expanded from some H for the first time. Since it is possible that the graph G may appear in 
at different stages, it must be guaranteed that 
doesn’t stop at a “wrong” node that corresponds to G.
Proposition 5. If 
stops, then 
is a max-min cycle packing of G.
Proof. Assume, 
terminates and
. In this case 
cor- responds to a node at stage
. Since the corresponding cycle packing 
is not maximum,
. Let 
be the path in 
induced by 
and let 
be the predecessor of 
on that path.
The only node in 
at stage 
corresponds to G (
). For the shortest path
, Theorem 1 gives
.
Let 
be the last common node of the paths 
and
. Since 
is expanded at some iteration of
, there must be a subgraph 
on the subpath 
of 
that belongs to X when 
terminates. Since this node is never selected in step 1 until 
stops (otherwise it would have been deleted from X in step 2), the inequality 
must hold. But then
is a contradiction. Hence, 
terminates at stage
, i.e. 
is maximum. 
Acknowledgements
We thank the Editor and the referees for their comments.
NOTES
2We will write “H Î X”, indicating that the node that corresponds to H belongs to X.