  We propose and study the graph-theoretical problem EXISTS-PMVC: the existence
of perfect matching under vertex-color constraints on graphs with bi-colored
edges. EXISTS-PMVC is of special interest because of its motivation from
quantum-state identification and quantum-experiment design, as well as its rich
expressiveness, i.e., EXISTS-PMVC naturally subsumes important constrained
matching problems, such as exact perfect matching. We give complexity and
algorithmic results for EXISTS-PMVC under two types of vertex color
constraints: (1) decision-diagram constraints (EXISTS-PMVC-DD) and (2)
symmetric constraints (EXISTS-PMVC-Sym).
  For EXISTS-PMVC-DD, we reveal its NP-hardness by a graph-gadget technique. We
prove that EXISTS-PMVC-Sym with a bounded number of colors
(EXISTS-PMVC-Sym-Bounded) is polynomially equivalent with Exact Perfect
Matching (XPM), which implies that EXISTS-PMVC-Sym-Bounded is in RNC on general
graphs and PTIME on planar graphs. Directly applying algorithms for XPM to
solve EXISTS-PMVC-Sym-Bounded is, however, impractical. We propose algorithms
that natively handle EXISTS-PMVC-Sym-Bounded with considerably better
complexity. Our novel results for EXISTS-PMVC provide insights into both
constrained matching and scalable quantum experiment design.
