We propose and study the graph theory problem PM-VC. This is an exact match under the vertex color constraint for a graph with two colored edges. PM-VC is of particular interest because of its motivation from the identification of quantum states and the design of quantum experiments, and its rich expressiveness. In other words, PM-VC naturally encompasses many constrained matching problems, such as strict exact matching. We present the complexity and algorithmic results of PM-VC under two kinds of vertex color constraints: 1) symmetry constraint (PM-VC-Sym) and 2) decision diagram constraint (PM-VC-DD).
Prove that PM-VC-Sym is in RNC via symbolic determinant algorithm. This can be non-randomized in planar graphs. Moreover, PM-VC-Sym can be represented in extended MSOs, facilitating the design of efficient dynamic programming algorithms for PM-VC-Sym on bounded tree width graphs. For PM-VC-DD, we reveal its NP hardness by the graph-gadget method. New PM-VC results provide insights into both constrained matching and scalable quantum experiment design.
