论文标题
量子风格的完美匹配在顶点颜色约束下
Quantum-Inspired Perfect Matching under Vertex-Color Constraints
论文作者
论文摘要
我们提出和研究存在图理论问题的存在：PMVC：在带有双色边缘的图形上存在完美匹配的情况下，存在完美匹配。存在PMVC引起了特别的兴趣，因为它来自量子状态识别和量子实验设计的动机，以及其丰富的表现力，即存在的PMVC自然含有重要的约束匹配问题，例如精确的完美匹配。在两种类型的顶点颜色约束下，我们给出了存在PMVC的复杂性和算法结果：（1）决策单数约束（存在PMVC-DD）和（2）对称约束（已存在PMVC-SYM）。 对于存在PMVC-DD，我们通过图形技术揭示其NP硬度。我们证明存在具有界数颜色数量的PMVC-SYM（存在PMVC-Sym结合）在多项式上等效，具有精确的匹配（XPM），这意味着存在于PMVC-MYNC中，在Planar图上的rnc中存在PMVC-sym-bonnc。然而，直接应用XPM算法求解存在PMVC-MYN-and-and-and-band-band-band-band of to。然而，不切实际。我们提出的算法是，存在于pMVC-sym的本地处理，其复杂性相当好。我们的新型PMVC结果提供了有关约束匹配和可扩展量子实验设计的见解。
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.
