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" [...]


  Payday Loans In Florida. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.