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.


  payday loans online. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.