ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let G=(V,E)G=(V,E) be a graph and let SS be a set of terminal pairs with ∣S∣=2|S|=2. The multicut dominant \textscMultC(G,S)\textsc{MultC}(G,S) is the dominant associated with multicut incidence vectors. Two-pair description conjecture. It is completely described by

xe≥0for all e∈E,x_e\geq 0\quad\text{for all }e\in E,

and

∑e∈(P)xe≥1\sum_{e\in(P)}x_e\geq 1

for each ss-tt path PP with {s,t}∈S\{s,t\}\in S. The claim would extend the known complete description for one terminal pair; the source presents the two-pair case as an open conjecture, while more efficient separation methods remain separate open questions.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.