|
The problem of determining the maximum size of a $C_k$-free $2$-matching (that is, a $2$-matching not containing cycles of length $k$) is a
much studied question of matching theory. Cornuéjols and Pulleyblank showed that deciding the existence of a $C_k$-free $2$-factor is NP-complete for
$k\ge 5$, while Hartvigsen gave an algorithm for the triangle-free case ($k=3$). The existence of a $C_4$-free 2-matching is still open.
The description of the $C_k$-free $2$-matching polytope is also of interest. Király showed that finding a maximum weight square-free 2-factor is
NP-complete even in bipartite graphs with $0-1$ weights, hence we should not expect a nice polyhedral description for $k\geq 4$. However, imposing
the condition that the graph has maximum degree 3, these problems become considerably easier. The polyhedral description of the triangle-free 2-factor
and 2-matching polytopes of subcubic simple graphs was given by Hartvigsen and Li. In this paper, we give slight generalizations of their nice results
by using a shrinking method inspired by Edmonds' maximum matching algorithm.
Considering the general case, a new class of valid inequalities for the triangle-free 2-matching polytope is introduced. With the help of these
inequalities, we propose a conjecture for the polyhedral description of the triangle-free 2-matching polytope of simple graphs.
Bibtex entry:
| AUTHOR | = | {B{\'e}rczi, Krist{\'o}f}, |
| TITLE | = | {The triangle-free 2-matching polytope of subcubic graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2012}, |
| NUMBER | = | {TR-2012-02} |