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

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

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

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

Cluster 2

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