**Tuesday, 13:15 - 13:40 h, Room: H 3013**

**Kristóf Bérczi**

Restricted *b*-matchings

**Abstract:**

A *C*_{ ≤ k}-free *2*-factor is a *2*-factor not containing cycles of length at most *k*. Cornuéjols and Pulleyblank showed that deciding the existence of such a subgraph is NP-complete for *k ≥ 5*. On the other hand, Hartvigsen proposed an algorithm for the triangle-free case (*k=3*). The existence of a *C*_{ ≤ 4}-free or *C*_{4}-free *2*-matching is still open (in the latter, triangles are allowed). Yet imposing the condition that the graph is subcubic (that is, the maximum degree of *G* is *3*), these problems become solvable.

Considering the maximum weight version of the problems, there is a firm difference between triangle- and square-free *2*-factors. Király showed that finding a maximum weight square-free *2*-factor is NP-complete even in bipartite graphs with *0-1* weights. On the other hand, for subcubic graphs, polynomial-time algorithms were given by Hartvigsen and Li, and recently by Kobayashi for the weighted *C*_{3}-free *2*-factor problem with an arbitrary weight function. The former result implies that we should not expect a nice polyhedral description of the square-free *2*-factor polytope. However, the latter suggests that the triangle-free case may be solvable.

Talk 1 of the invited session Tue.2.H 3013

**"Matching and related problems"** [...]

Cluster 2

**"Combinatorial optimization"** [...]