ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let XPM denote exact perfect matching: given a graph with blue/red-colored edges and an integer kk, determine whether there exists a perfect matching containing exactly kk red edges. Let PM-VC-Sym denote perfect matching under vertex-color constraints with symmetric color constraints. Polynomial-time reducibility is denoted by ≤P\le_P, and polynomial-time equivalence by =P=_P.

Hardness conjecture.

XPM=PPM-VC-Sym.\mathrm{XPM} =_P \mathrm{PM\text{-}VC\text{-}Sym}.

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 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.