Uniform covers by tours

From himtp
Revision as of 13:13, 23 September 2015 by Wegner (Talk | contribs) (What is known?)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

(suggested by András Sebő)

Problem Statement

Let G be a cubic 3-edge-connected graph.

Conjecture: The uniform 8/9 function on the edges is in the convex hull of tours. (Connected, Eulerian spanning subgraphs of 2G.)

What is known?

Since 2/3 is in the subtour-elimination polytope (HK) of such graphs, this follows from the famous conjecture about integrality gap 4/3, equivalent to 4/3 HK being contained in the convex hull of (incidence vectors) of tours. It contains, in turn, the 4/3 integrality gap of the maximum size of tours in cubic 3-edge-connected graphs. For the all 1 function instead of 8/9 it is a simple exercise if you know the tree polytope and the T-join polytope.

Please add comments here