The triangle-free 2-matching polytope of subcubic graphs

Kristóf Bérczi


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-02}

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