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


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 C4-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 C3-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


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(n3) 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(n3). We then improve this time complexity to O(n2 log4 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


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.


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra No RX influence on blood clots.