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


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.


Talk 1 of the invited session Tue.2.H 3013
"Matching and related problems" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.