Circuit covers in series-parallel mixed graphs
Orlando Lee1
and Yoshiko Wakabayashi1 
| (1) |
Instituto de Matemática e Estatística, Universidade de SÃo Paulo, Rua do MatÃo 1010, 05508-900 SÃo Paulo, SP, Brazil |
Abstract
A mixed graph is a graph that contains both edges and arcs. Given a nonnegative integer weight function p on the edges and arcs of a mixed graph M, we wish to decide whether (M,p) has a circuit cover, that is, if there is a list of circuits in M such that every edge (arc) e is contained in exactly p(e) circuits in the list. When M is a directed graph or an undirected graph with no Petersen graph as a minor, good necessary and sufficient conditions are
known for the existence of a circuit cover. For general mixed graphs this problem is known to be NP-complete. We provide necessary
and sufficient conditions for the existence of a circuit cover of (M, p) when M is a series-parallel mixed graph, that is, the underlying graph of M does not have Ka as a minor. We also describe a polynomial-time algorithm to find such a circuit cover, when it exists. Further, we show that
p can be written as a nonnegative integer linear combination of at most m incidence vectors of circuits of M, where m is the number of edges and arcs. We also present a polynomial-time algorithm to find a minimum circuit in a series-parallel
mixed graph with arbitrary weights. Other results on the fractional circuit cover and the circuit double cover problem are
discussed.
This work has been partially supported by FAPESP (Proc. 96/04505-2), CNPq (Proc. 304527/89-0), CAPES (Proc. 3302006-0) and
PRONEX (Project 107/97).
References secured to subscribers.