Sufficiency of the NR-facet condition for parsimonious relaxations

From papers

Let PnP_n be the Graphical Traveling Salesman Polyhedron, let GB\mathcal G_B be the graph associated with a relaxation RB\mathcal R_B, and call a facet of PnP_n an NR-facet when it has the stated non-rank property. Parsimonious-relaxation conjecture. If every connected component of GB\mathcal G_B contains a vertex corresponding to an NR-facet of PnP_n, then the relaxation RB\mathcal R_B has the parsimonious property. This conjectures that the necessary condition established in the cited theorem is also sufficient; the supplied text gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dirk Oliver Theis, “On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra”, arXiv:0712.1269 (2009).

Solutions 0

No solutions have been posted yet.