# Item

ITEM ACTIONSEXPORT

Released

Report

#### Restricted 2-factor polytopes

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-97-1-006-1.pdf

(Any fulltext), 308KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Cunningham, W. H., & Wang, Y.(1997). *Restricted 2-factor
polytopes* (MPI-I-1997-1-006). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-9F73-8

##### Abstract

The optimal $k$-restricted 2-factor problem consists of finding,
in a complete undirected graph $K_n$, a minimum cost 2-factor
(subgraph having degree 2 at every node) with all components having more
than $k$ nodes.
The problem is a relaxation of the well-known symmetric travelling
salesman problem, and is equivalent to it when $\frac{n}{2}\leq k\leq n-1$.
We study the $k$-restricted 2-factor polytope. We present a large
class of valid inequalities, called bipartition
inequalities, and describe some of their properties; some of
these results are new even for the travelling salesman polytope.
For the case $k=3$, the triangle-free 2-factor polytope,
we derive a necessary and sufficient condition for such inequalities
to be facet inducing.