TR-2012-02

The triangle-free 2-matching polytope of subcubic graphs

Kristóf Bérczi



Abstract

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:

@techreport{egres-12-02,
AUTHOR = {B{\'e}rczi, Krist{\'o}f},
TITLE = {The triangle-free 2-matching polytope of subcubic graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-02}
}


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