Coauthors: D. Dereniowski, B. Ries, and Y. Zwols

We consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not, we show that several questions about the length of the sequence are computationally intractable. A recent paper characterizes so-called OLOP (Overall Local Pooling) graphs, a class of graphs for which similar matching-related problems are tractable (namely, in an online distributed wireless network scheduling setting). We therefore focus on these graphs. In particular, we show that deciding whether a given OLOP graph has a matching sequence of length at most k can be done in linear time. In case the answer is affirmative, we show how to construct, in quadratic time, the matching sequence of length at most k. Finally, we prove that, for OLOP graphs, the length of a shortest sequence does not exceed the least common denominator of the fractions r(e), leading to a pseudopolynomial-time algorithm for minimizing the length of the sequence. Following Seymour conjecture, we conjecture that a shortest sequence does not exceed twice the least common denominator of the fractions r(e) for general graphs. We then show that this conjecture holds for all graphs with at most 10 vertices.