For an undirected graph and a fixed integer k, a 2-matching is said to be k-restricted if it has no cycle of length k or less.
The problem of finding a maximum k-restricted 2-matching is polynomially solvable when k >= 3,
and NP-hard when k >= 5.
On the other hand,
the degree sequences of the k-restricted 2-matchings form a jump system for k <= 3,
and do not always form a jump system for k >= 5,
which is consistent with the polynomial solvability of the maximization problem.
In 2002,
Cunningham conjectured that the degree sequences of
4-restricted 2-matchings form a jump system and
the maximum 4-restricted 2-matching can be found in polynomial time.
In this paper, we show that the first conjecture is true, that is,
the degree sequences of
4-restricted 2-matchings form a jump system.
We also show
that
the weighted 4-restricted 2-matchings in a bipartite graph
induce
an M-concave function on the jump system
if and only if
the weight function is vertex-induced on every square.
This result is also consistent with the
polynomial solvability of the weighted 4-restricted 2-matching problem in bipartite graphs.
Bibtex entry:
@techreport{egres-10-04,
AUTHOR | = | {Kobayashi, Yusuke and Szab{\'o}, J{\'a}cint and Takazawa, Kenjiro}, |
TITLE | = | {A proof to Cunningham's conjecture on restricted subgraphs and jump systems}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2010}, |
NUMBER | = | {TR-2010-04} |