ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let MOTJ denote the problem of deciding, for an undirected graph G=(V,E)G=(V,E) with rational edge weights w:E→Qw:E\to\mathbb{Q}, a set T⊆VT\subseteq V, and k∈Qk\in\mathbb{Q}, whether there is an odd TT-join of total weight at most kk. Let SOC denote the corresponding problem of finding a minimum-weight odd cycle. Polynomial-time solvability conjecture. MOTJ and SOC can be solved in polynomial time. A randomized polynomial-time algorithm places MOTJ in the class RP⁡\operatorname{RP}, so polynomial-time solvability remains conjectural; the source presents these problems as potentially more tractable than the shortest odd path problem.

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.