Quantum-Inspired Perfect Matching under Vertex-Color Constraints

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 many 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) symmetric constraints (EXISTS-PMVC-Sym) and 2) decision-diagram constraints (EXISTS-PMVC-DD). For EXISTS-PMVC-DD, we reveal its NP-hardness by a graph-gadget-based technique. We prove that EXISTS-PMVC-Sym with a bounded number of colors (EXISTS-PMVC-Sym-Bounded) is as hard as Exact Perfect Matching (XPM), which indicates 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 due to the overhead brought by the reduction. Therefore, we propose algorithms that natively handle EXISTS-PMVC-Sym-Bounded with significantly better efficiency. Our novel results for EXISTS-PMVC provide insights into both constrained matching and scalable quantum experiment design.