Polynomial-time solvability conjecture for MOTJ and SOC
Statement
Let MOTJ denote the problem of deciding, for an undirected graph with rational edge weights , a set , and , whether there is an odd -join of total weight at most . 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 , 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.