TR-2010-04

A proof to Cunningham's conjecture on restricted subgraphs and jump systems

Yusuke Kobayashi, Jácint Szabó, Kenjiro Takazawa



Abstract

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}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!