Quantum-Inspired Perfect Matching under Vertex-Color Constraints

We propose and study the graph-theoretical problem PM-VC: perfect matching under vertex-color constraints on graphs with bi-colored edges. PM-VC is of special interest because of its motivation from quantum-state identification and quantum-experiment design, as well as its rich expressiveness, i.e., PM-VC subsumes many constrained matching problems naturally, such as exact perfect matching. We give complexity and algorithmic results for PM-VC under two types of vertex color constraints: 1) symmetric constraints (PM-VC-Sym) and 2) decision-diagram constraints (PM-VC-DD). We prove that PM-VC-Sym is in RNC via a symbolic determinant algorithm, which can be derandomized on planar graphs. Moreover, PM-VC-Sym can be expressed in extended MSO, which encourages our design of an efficient dynamic programming algorithm for PM-VC-Sym on bounded-treewidth graphs. For PM-VC-DD, we reveal its NP-hardness by a graph-gadget technique. Our novel results for PM-VC provide insights to both constrained matching and scalable quantum experiment design.