Uniform covers by tours

From himtp
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