Extreme rays and diameter conjecture for the oriented-multicut skeleton

Let QMETnQMET_n be the cone of quasi-semimetrics and OMCUTnOMCUT_n the cone generated by oriented multicuts. Let GOMCUTnG_{OMCUT_n} be the skeleton graph of OMCUTnOMCUT_n, whose nodes are its extreme rays and whose edges join adjacent extreme rays. A dominating clique is a complete subgraph such that every node is adjacent to at least one of its elements.

Oriented-multicut skeleton conjecture. (i) All oriented multicuts are extreme rays of QMETnQMET_n. (ii) The oriented cuts form a dominating clique in GOMCUTnG_{OMCUT_n}; consequently, the diameter of GOMCUTnG_{OMCUT_n} is 22 or 33 for every n4n\geq 4.

The assertions were presented as conjectural general results about the oriented-multicut cone; the surrounding text does not provide a general proof or resolution.

Sources & referencesView supporting material

Primary source

M. Deza, M. Dutour and E. Panteleeva, “Small cones of oriented semi-metrics”, arXiv:math/0111145 (2002).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.