Circuit Covers in Series-Parallel Mixed Graphs

摘要

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 htere is a list of circuits in M such that every edge e is contained in exactly P(e) circuits in the list. When M is a directed graph or an undrected graph with no Petersen graph as a minor, god necessary and sufficient condifiotns are known for the existence of a circuit cover. For gneral mixed graphs this problem is known to be NP-complete. We provide necessary and sufficient ocnditions 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 K sub 4 as a minor. We also describe a polynomial-time algorithm to find such a circuit cover, when it exists. Frther, we show that p can be written as a nonnegative integer linear ocmbinatin 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 oduble cover problem are discussed.