MATHEMATICAL ENGINEERINGTECHNICAL REPORTS

On Odd-Cycle-Symmetry of Digraphs

Naonori KAKIMURA and Yusuke KOBAYASHI(Communicated by Satoru IWATA)METR 2005–36

November 2005

DEPARTMENT OF MATHEMATICAL INFORMATICSGRADUATE SCHOOL OF INFORMATION SCIENCE AND TECHNOLOGYTHE UNIVERSITY OF TOKYOBUNKYO-KU, TOKYO 113-8656, JAPANWWW page: http://www.i.u-tokyo.ac.jp/mi/mi-e.htm

The METR technical reports are published as a means to ensure timely dissemination ofscholarly and technical work on a non-commercial basis. Copyright and all rights therein
are maintained by the authors or by other copyright holders, notwithstanding that they
have oﬀered their works here electronically. It is understood that all persons copying thisinformation will adhere to the terms and constraints invoked by each author’s copyright.
These works may not be reposted without the explicit permission of the copyright holder.

On Odd-Cycle-Symmetry of Digraphs
Naonori KAKIMURA ∗Yusuke KOBAYASHI ∗November, 2005

Abstract
A digraph is odd-cycle-symmetric if every arc in any elementary odd directed cycle has the reversearc. This concept arises in the context of the even factor problems, which generalize the path-matchingproblems. While the even factor problem is NP-hard in general digraphs, it is solvable in polynomial
time for odd-cycle-symmetric digraphs. This paper provides a characterization of odd-cycle-symmetricdigraphs and presents a linear time algorithm to determine whether a given digraph is odd-cyclesymmetric or not. The paper also discusses the weighted version.

1

Introduction

A directed graph (digraph) is odd-cycle-symmetric if every arc in any elementary odd directed cycle has
the reverse arc. Odd-cycle-symmetric digraphs were introduced in the context of the even factor problems.
An even factor in a digraph is a collection of vertex-disjoint directed paths and even directed cycles,
which is introduced by Cunningham and Geelen [2] as a generalization of a path-matching [1]. It is known
that the problem of ﬁnding a maximum even factor is NP-hard in general, but solvable in polynomial
time if the digraph is weakly symmetric [2], which is a special case of the odd-cycle-symmetric digraphs.
A digraph is said to be weakly symmetric if every arc in any directed cycle has the reverse arc. We say adigraph is symmetric if every arc has the reverse arc. Recently, Pap [5] devised a polynomial algorithm
for the even factor problem in an odd-cycle-symmetric digraph.
This paper gives a characterization of the odd-cycle-symmetric digraphs. For this purpose, we introduce the notion of a cycle-connected digraph. A digraph is said to be cycle-connected if it is stronglyconnected and its underlying graph is 2-connected. A digraph is said to be bipartite if its underlying graphis bipartite. Our main result (Theorem 1) asserts that a cycle-connected digraph is odd-cycle-symmetric
if and only if it is symmetric or bipartite.
A digraph can be decomposed into cycle-connected components. This decomposition preserves oddcycle-symmetry. Therefore, it follows from Theorem 1 that an odd-cycle-symmetric digraph can bedecomposed into bipartite digraphs and symmetric digraphs. Since the decomposition can be done inlinear time with the aid of basic graph algorithms, odd-cycle-symmetry can be recognized in linear time.
Note that a weakly symmetric digraph can be decomposed into symmetric cycle-connected components.
Thus the class of odd-cycle-symmetric digraphs is slightly broader than that of weakly symmetric digraphs.
∗Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo,
Bunkyo-ku Tokyo 113-8656, Japan ({Naonori Kakimura,Yusuke Kobayashi}@mist.i.u-tokyo.ac.jp).

1

In addition, we discuss odd-cycle-symmetry of weighted digraphs. Let w be a weight function deﬁned
on the arc set of an odd-cycle-symmetric digraph G. Then (G, w) is said to be odd-cycle-symmetric if thesum of the weights of the arcs in any elementary odd directed cycle C is the same as that of its reverse
cycle C̄.
For an odd-cycle-symmetric weighted digraph (G, w), Király and Makai [4] presented a linear programthat describes the maximum weight even factor problem, and proved the dual integrality. Takazawa [7]presented a combinatorial primal-dual algorithm to ﬁnd a maximum weight even factor in an odd-cyclesymmetric weighted digraph. His algorithm also gives a constructive proof of the dual integrality.
In the same way as the unweighted case, we deal with a cycle-connected weighted digraph G. Theorem
1 implies that, if G is odd-cycle-symmetric, then it is bipartite or symmetric. If G is bipartite, then(G, w) is clearly odd-cycle-symmetric for any weight function w. We show that, for a digraph G that isnot bipartite but symmetric, (G, w) is odd-cycle-symmetric if and only if there exists a function p on thevertex set such that d(a) = p(v) − p(u) for each arc a = (u, v) in G, where d(a) = w(a) − w(ā) for eacharc a and its reverse arc ā. Odd-cycle-symmetry of a weighted digraph can be tested in linear time bychecking the existence of such function p.
We conclude this section by giving some deﬁnitions and notations. In this paper, we consider
digraphs with no loops and no multiple arcs. We denote by (u, v) the arc from u to v. We say
P = (v1 , a1 , . . . , vk , ak , vk+1 ) is a path if ai = (vi , vi+1 ) for 1 ≤ i ≤ k. A path is said to be even if
k is even, and odd if k is odd. If vi 6= vj for i 6= j, then P is said to be elementary. We call v1 and vk+1
the end vertices of P , and the other vertices the interior vertices. A cycle C is a path which ends at thevertex it begins with, namely, C = (v1 , a1 , . . . , vk , ak , v1 ). If vi 6= vj (i 6= j, 1 ≤ i, j ≤ k), then C is said
to be elementary.
For paths P1 = (v1 , a1 , . . . , vk , ak , vk+1 ) and P2 = (vk+1 , ak+1 , . . . , vl , al , vl+1 ), we denote by P1 · P2 thepath (v1 , a1 , . . . , vk , ak , vk+1 , ak+1 , . . . , vl+1 ). For a subgraph G0 and a path P in a digraph G, we denoteby G0 + P the subgraph that consists of the vertices and the arcs of G0 and P .
For an arc a, we denote by ā the reverse arc (if exists). For a path P = (v1 , a1 , . . . vk , ak , vk+1 ), thereverse path (if exists) is denoted by P̄ , that is P̄ = (vk+1 , a¯k , vk , . . . , a¯1 , v1 ).

2

Odd-Cycle-Symmetry

Our main result is the following theorem.
Theorem 1. A cycle-connected digraph G is odd-cycle-symmetric if and only if G is bipartite or symmetric.
In order to prove Theorem 1, we use the ear decomposition of cycle-connected digraphs. Let G be adigraph, and G0 a subgraph of G. We say that an elementary path P in G is an ear of G0 if G0 contains
both of the end vertices of P , but no interior vertices and no arcs. An ear is said to be proper if its
end vertices are distinct. Then the following lemma holds for cycle-connected digraphs. This lemma wasshown by Grötschel [3], where cycle-connected digraphs are called strong blocks.
Lemma 2. Let G be a cycle-connected digraph, and G0 a subgraph of G with at least two vertices. If
G0 6= G then G0 has a proper ear.

2Proof. Assume that there exist no proper ears of G0 = (V 0 , A0 ). Let v1 , . . . , vh ∈ V 0 be all vertices fromwhich some arcs in A \ A0 leave, and Si be the set of vertices which can be reached from vi without
using arcs of A0 . Since G0 has no proper ears, V 0 ∩ Si = {vi } for each i. Since G is strongly connected,
vj is reachable from any vertex in Sj . Hence Si ∩ Sj = ∅ for i 6= j, so S1 , . . . , Sh is a partition of(V \ V 0 ) ∪ {v1 , . . . , vh }. Since there are no arcs between Si and Sj for i 6= j, we can separate Si \ {vi }from V \ Si by deleting vi , which contradicts that the underlying graph of G is 2-connected.
We also give a characterization of digraphs without elementary odd cycles.
Lemma 3. A strongly connected digraph G has no elementary odd cycles if and only if G is bipartite.
Proof. The necessity is obvious. To see the suﬃciency, suppose G = (V, A) has no elementary odd cycles.
Then G has no odd cycles. Let a ∈ A be an arc from u to v such that ā 6∈ A. Since G is strongly
connected and has no odd cycles, there exists an odd path P from v to u. Then there exist no even paths
from u to v, and hence the digraph obtained from G by adding the reverse arc ā also has no odd cycles.
Thus G0 = (V, A ∪ Ā) has no odd cycles, which means G is bipartite.
By these lemmas, we have the following proposition.
Proposition 4. Let G be a cycle-connected odd-cycle-symmetric digraph that is not bipartite. Thereexists a sequence G0 , G1 , . . . , Gk = G of subgraphs such that the following (A) and (B) hold.
(A) G0 consists of an elementary odd cycle C and its reverse cycle C̄.
(B) Gi+1 is obtained from Gi by adding Pi and P̄i , where Pi is a proper ear having the reverse path P̄i ,for i = 0, 1, . . . , k − 1.
Furthermore, the sequence G0 , G1 , . . . , Gk satisﬁes the following (C) and (D).
(C) There exist both an elementary even path and an elementary odd path from u to v in Gi = (Vi , Ai )for every vertex pair u, v ∈ Vi .
(D) If P is a proper ear of Gi , then every arc of P has the reverse arc.
Proof. By Lemma 3, G has an elementary odd cycle C. Hence there exists a subgraph G0 satisfying(A). Since Lemma 2 and the condition (D) assure that there exists a sequence G0 , G1 , . . . , Gk = G ofsubgraphs such that (A) and (B) hold, it suﬃces to show (C) and (D).
We prove (C) and (D) by induction on i. Obviously, G0 satisﬁes (C) and (D). Suppose (C) and (D)hold for i = j. Let Pj be a proper ear of Gj from sj to tj . Then the reverse path P¯j exists by theinduction hypothesis of the condition (D). Consider Gj+1 = Gj + Pj + P¯j .
We ﬁrst show that the condition (C) holds for i = j + 1.
1. Suppose u, v ∈ Vj . Then it follows from the induction hypothesis that there exist both an elementaryeven path and an elementary odd path from u to v in Gj+1 .
2. Suppose u ∈ Vj and v ∈ Vj+1 \ Vj . Let P 0 be a path from sj to v along Pj . Since there exist both anelementary even path Pe and an elementary odd path Po from u to sj in Gj , one of Pe · P 0 and Po · P 0
is an elementary even path, and the other is an elementary odd path. If v ∈ Vj and u ∈ Vj+1 \ Vj ,we can prove that there exist both an elementary even path and an elementary odd path from u tov in a similar way.
3

3. Suppose u, v ∈ Vj+1 \ Vj . Without loss of generality we assume sj , v, u, and tj appear on Pj in thisorder. Let P 0 be a path from u to tj along Pj , and P 00 a path from sj to v along Pj . Since there
exist both an elementary even path Pe and an elementary odd path Po from tj to sj in Gj , one of
P 0 · Pe · P 00 and P 0 · Po · P 00 is an elementary even path, and the other is an elementary odd path.
Thus there exist both an elementary even path and an elementary odd path from u to v in Gj+1 for every
vertex pair u, v ∈ Vj+1 .
We next show that the condition (D) holds for i = j + 1. Let P be a proper ear of Gj+1 from s to t.
Since there exist both an elementary even path Pe and an elementary odd path Po from t to s in Gj+1 ,either P · Pe or P · Po is an elementary odd cycle. Hence every arc of P has the reverse arc.
We are now ready to prove Theorem 1. The necessity is obvious, as bipartite digraphs have no odd
cycles. To prove the suﬃciency, assume that a digraph G is odd-cycle-symmetric. If G is not bipartite,then it is symmetric by Proposition 4, which completes the proof of Theorem 1.
Theorem 1 leads to a linear time algorithm for recognizing odd-cycle-symmetry of a digraph as follows.
Corollary 5. Given a digraph G, we can determine whether G is odd-cycle-symmetric in O(m + n) time,
where m and n are the numbers of the arcs and vertices, respectively.
Proof. We can decompose G into strongly connected components in linear time [8]. We can also decompose
each strongly connected component into the components whose underlying graphs are 2-connected inlinear time [6, 8]. Note that these components are also strongly connected, and hence cycle-connected.
Since every cycle in G is contained in some component, G is odd-cycle-symmetric if and only if every
component is odd-cycle-symmetric. By Theorem 1, it suﬃces to check if every obtained component D
is bipartite or symmetric. We can check whether D is bipartite or not in O(mD + nD ) time, where mD
and nD represent the numbers of the arcs and vertices of D, respectively. Checking the symmetry of D
requires O(mD + nD ) time. Thus we can determine whether G is odd-cycle-symmetric or not in O(m + n)
time.

3

Odd-Cycle-Symmetry of Weighted Digraphs

Let G = (V, A) be an odd-cycle-symmetric digraph, and w be a weight function deﬁned on the arc set A.
We write w(P ) = Σa∈P w(a) for a path P , and w(C) = Σa∈C w(a) for a cycle C. Then (G, w) is said tobe odd-cycle-symmetric if w satisﬁes that w(C) = w(C̄) for every elementary odd cycle C.
If an arc a has the reverse arc ā, then d(a) denotes w(a) − w(ā). Note that w(C) = w(C̄) for a cycle
C is equivalent to d(C) = 0.
Theorem 6. Let G = (V, A) be a cycle-connected symmetric digraph that is not bipartite. A weighted
digraph (G, w) is odd-cycle-symmetric if and only if there exists a function p on V such that d(a) =p(v) − p(u) for each arc a = (u, v) ∈ A.
Proof. The necessity is obvious, as the existence of such a function p implies that w(C 0 ) = w(C̄ 0 ) for every
elementary cycle C 0 . To prove the suﬃciency, we assume that (G, w) is odd-cycle-symmetric. A digraphG has an elementary odd cycle C by Lemma 3.
Let G0 , G1 , . . . , Gk = G be a sequence of subgraphs of G which satisﬁes the following conditions.
1. The subgraph G0 consists of C and C̄.
4

2. For i = 0, 1, . . . , k − 1, Gi+1 = Gi + Pi + P̄i , where Pi is a proper ear of Gi from si to ti .
Proposition 4 guarantees the existence of such a sequence.
We show by induction on i that Gi = (Vi , Ai ) has a function pi on Vi such that d(a) = pi (v) − pi (u)for each arc a = (u, v) ∈ Ai . It is trivial that G0 satisﬁes this property. Suppose Gj satisﬁes the property.
Consider Gj+1 = Gj + Pj + P¯j .
By Proposition 4, there exist both an elementary even path Pe and an elementary odd path Po fromtj to sj in Gj , and either Pj · Pe or Pj · Po is an elementary odd cycle. Furthermore, Pe and Po satisfyd(Pe ) = d(Po ) = pj (sj ) − pj (tj ). Thus we have d(Pj ) = pj (tj ) − pj (sj ). We deﬁne a function pj+1 on Vj+1
as follows. If v ∈ Vj , then we set pj+1 (v) = pj (v). Otherwise, we set pj+1 (v) = pj (sj ) + d(Pv ), where Pv isa path from sj to v along Pj . Then d(a) = pj+1 (v) − pj+1 (u) holds for each arc a = (u, v) ∈ Aj+1 . Thus
Gj+1 satisﬁes the property.
Since G = Gk , there exists a function p on V such that d(a) = p(v) − p(u) for each arc a = (u, v) ∈A.
Corollary 7. Given a weighted digraph (G, w), we can determine whether (G, w) is odd-cycle-symmetricin O(m + n) time, where m and n are the numbers of the arcs and vertices, respectively.
Proof. As in the the proof of Corollary 5, recognizing odd-cycle-symmetry of (G, w) can be reduced tothat of cycle-connected digraphs in linear time. Hence we may assume G = (V, A) is cycle-connected. Acycle-connected weighted digraph (G, w) is odd-cycle-symmetric if and only if G is bipartite, or G is asymmetric graph with a function p such that d(a) = p(v) − p(u) for each arc a = (u, v) ∈ A. Whether G isbipartite or not can be checked in linear time. It also takes a linear time to check whether G is symmetricor not. The existence of the function p can be checked in O(m + n) time as follows. Take a vertex r ∈ Vand ﬁnd a directed spanning tree T in G rooted at r. For each vertex v ∈ V , let Pv be the unique pathfrom r to v in T , and set p(v) := d(Pv ). Note that p(r) = 0. Then for each arc a = (u, v) ∈ A \ T , checkif d(a) = p(v) − p(u) holds.
Thus we can determine whether (G, w) is odd-cycle-symmetric or not in linear time.

Acknowledgments
The authors thank Satoru Iwata for his helpful advise on the manuscript.

References[1] W. H. Cunningham and J. F. Geelen, The optimal path-matching problem, Combinatorica, 17 (1997),315–337.
[2] W. H. Cunningham and J. F. Geelen, Vertex-disjoint directed paths and even circuits, manuscript,2001.
[3] M. Grötschel, On minimal strong blocks, J. Graph Theory, 3 (1979), 213–219.
[4] T. Király and M. Makai, On polyhedra related to even factors, in D. Bienstock and G. Nemhauser,eds., Integer Programming and Combinatorial Optimization: Proceedings of the 10th International
IPCO Conference, LNCS 3064, Springer-Verlag, 2004, 416–430.
5[5] G. Pap, A combinatorial algorithm to ﬁnd a maximum even factor, in M. Jünger and V. Kaibel, eds.,
Integer Programming and Combinatorial Optimization: Proceedings of the 11th International IPCO
Conference, LNCS 3509, Springer-Verlag, 2005, 66–80.
[6] K. Paton, An algorithm for the blocks and cutnodes of a graph, Communications of the ACM, 14(1971), 468–475.
[7] K. Takazawa, A weighted even factor algorithm, METR 2005-17, University of Tokyo, July 2005,(available from http://www.keisu.t.u-tokyo.ac.jp/Research/techrep.0.html).
[8] R. Tarjan, Depth-ﬁrst search and linear graph algorithms, SIAM J. Computing, 1 (1972), 146–160.

6