The conjecture that PM-VC-Sym is as hard as exact perfect matching
Statement
Let XPM denote exact perfect matching: given a graph with blue/red-colored edges and an integer , determine whether there exists a perfect matching containing exactly red edges. Let PM-VC-Sym denote perfect matching under vertex-color constraints with symmetric color constraints. Polynomial-time reducibility is denoted by , and polynomial-time equivalence by .
Hardness conjecture.
XPM is known to be in randomized NC, while the paper proves that PM-VC-Sym with a bounded number of colors is also in randomized NC. The conjecture proposes that PM-VC-Sym is no harder than XPM despite allowing more than two colors and bi-colored edges; whether the asserted polynomial-time equivalence holds remains open in the supplied text.
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.