## Invited Session Tue.2.H 3013

#### Tuesday, 13:15 - 14:45 h, Room: H 3013

**Cluster 2: Combinatorial optimization** [...]

### Matching and related problems

**Chair: Gyula Pap**

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

**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.

**Tuesday, 13:45 - 14:10 h, Room: H 3013, Talk 2**

**Kenjiro Takazawa**

Covering cuts in bridgeless cubic graphs

**Coauthors: Sylvia Boyd, Satoru Iwata**

**Abstract:**

In this talk we are interested in algorithms for finding *2*-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. We present an algorithm for finding a minimum-weight *2*-factor covering all the *3*-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such *2*-factors and that of perfect matchings intersecting all the *3*-edge cuts in exactly one edge. We further give an algorithm for finding a *2*-factor covering all the *3*- and *4*-edge cuts in bridgeless cubic graphs. Both of these algorithms run in *O(n*^{3}) time, where *n* is the number of vertices.

As an application of the latter algorithm, we design a *6/5*-approximation algorithm for finding a minimum *2*-edge-connected subgraph in *3*-edge-connected cubic graphs, which improves upon the previous best ratio of *5/4*. The algorithm begins with finding a *2*-factor covering all *3*- and *4*-edge cuts, which is the bottleneck in terms of complexity, and thus it has running time *O(n*^{3}). We then improve this time complexity to *O(n*^{2} *log*^{4} n) by relaxing the condition of the initial *2*-factor and elaborating the subsequent processes.

**Tuesday, 14:15 - 14:40 h, Room: H 3013, Talk 3**

**David Hartvigsen**

A generalized *k*-matching problem

**Coauthor: Yanjun Li**

**Abstract:**

A simple *k*-matching in a graph is a subgraph all of whose nodes have degree at most *k*. The problem of finding a simple *k*-matching with a maximum number of edges is well studied and results include a max-min theorem and polynomial-time algorithm. A simple *k*-matching is called *j*-restricted if each connected component has more than *j* edges. In this talk we consider the problem of finding *j*-restricted simple *k*-matchings that have a maximum number of edges. We present a max-min theorem and polynomial-time algorithm when *j < k*. Previous work on this problem considers the special case *j**.*

* *

*
*