Triangle-free 2-matchings

We consider the problem of finding a maximum size triangle-free $2$-matching in a graph $G=(V,E)$. A (simple) $2$-matching is any subset of the edges such that each vertex is incident to at most two edges from the subset. We present a fast combinatorial algorithm for the problem. Our algorithm and its analysis are significantly simpler than the very complicated result by Hartvigsen from 1984 as well as its recently published journal version. Moreover, our algorithm with running time $O(|V||E|)$ is faster than the one by Hartvigsen having running time $O(|V|^3|E|^2)$. Let $M$ denote any triangle-free $2$-matching. An $M$-alternating path or cycle $P$ is {\em feasible} if $M \oplus P$ is a triangle-free $2$-matching. It has been proven before that for any $M$ which is not maximum the graph contains a feasible $M$-augmenting path. One of the key new observations is that to facilitate the search for such a feasible augmenting path $P$ we can employ {\em half-edges}. A {\em half-edge} of edge $e$ is, informally speaking, a half of $e$ containing exactly one of its endpoints. To find an augmenting path, whose application does not create any triangle we forbid some edges to be followed by certain others. This operation can be thought of as using gadgets, in which some pairs of edges get disconnected via the removal of appropriate half-edges. We also prove a decomposition theorem for triangle-free $2$-matchings, largely the same as the decomposition from versions 1-6 of this paper and which is simpler and stronger than the one posted by Kobayashi and Noguchi in \cite{Noguchi}.