2025-11-13T16:28:10.775883

A CSP approach to Graph Sandwich Problems

Bodirsky, Guzmán-Pro
The \emph{Sandwich Problem} (SP) for a graph class $\calC$ is the following computational problem. The input is a pair of graphs $(V,E_1)$ and $(V,E_2)$ where $E_1\subseteq E_2$, and the task is to decide whether there is an edge set $E$ where $E_1\subseteq E \subseteq E_2$ such that the graph $(V,E)$ belongs to $\calC$. In this paper we show that many SPs correspond to the constraint satisfaction problem (CSP) of an infinite $2$-edge-coloured graph $H$. We then notice that several known complexity results for SPs also follow from general complexity classifications of infinite-domain CSPs, suggesting a fruitful application of the theory of CSPs to complexity classifications of SPs. We strengthen this evidence by using basic tools from constraint satisfaction theory to propose new complexity results of the SP for several graph classes including line graphs of multigraphs, line graphs of bipartite multigraphs, $K_k$-free perfect graphs, and classes described by forbidding finitely many induced subgraphs, such as $\{I_4,P_4\}$-free graphs, settling an open problem of Alvarado, Dantas, and Rautenbach (2019). We also construct a graph sandwich problem which is in coNP, but neither in P nor coNP-complete (unless P = coNP).
academic

A CSP approach to Graph Sandwich Problems

基本信息

  • 论文ID: 2510.09128
  • 标题: A CSP approach to Graph Sandwich Problems
  • 作者: Manuel Bodirsky, Santiago Guzmán-Pro (TU Dresden)
  • 分类: cs.DM (离散数学), cs.CC (计算复杂性), math.CO (组合数学)
  • 发表时间: 2025年10月13日
  • 论文链接: https://arxiv.org/abs/2510.09128

摘要

图夹心问题(Graph Sandwich Problem, SP)是图论中的重要计算问题。对于图类C\mathcal{C}，其夹心问题定义为：给定两个图(V,E1)(V,E_1)和(V,E2)(V,E_2)且E1⊆E2E_1 \subseteq E_2，判断是否存在边集EE使得E1⊆E⊆E2E_1 \subseteq E \subseteq E_2且图(V,E)(V,E)属于C\mathcal{C}。本文证明了许多夹心问题等价于无穷2-边着色图HH的约束满足问题(CSP)，并利用CSP理论为多个图类的夹心问题提供了新的复杂性结果，包括多重图的线图、二部多重图的线图、KkK_k-free完美图等，解决了Alvarado等人(2019)提出的开放问题。

研究背景与动机

问题重要性

  1. 理论意义：图夹心问题是图论中的经典问题，由Golumbic等人于1995年引入，是图识别问题的自然推广
  2. 计算复杂性：夹心问题至少与相应的图识别问题一样困难，其复杂性分类是算法图论的重要课题
  3. 开放问题：完美图的夹心问题复杂性仍未确定，被认为是该领域最重要的开放问题之一

现有方法局限性

  1. 缺乏统一框架：现有研究多采用针对特定图类的专门技术，缺乏通用的分析方法
  2. 证明复杂：传统的硬度证明通常需要复杂的归约构造
  3. 理论工具有限：缺少系统性的理论工具来分析夹心问题的复杂性

研究动机

本文旨在建立图夹心问题与约束满足问题之间的联系，利用CSP理论的成熟工具为夹心问题提供统一的分析框架。

核心贡献

  1. 理论框架建立：证明了满足特定条件的图类的夹心问题等价于2-边着色图的CSP
  2. 复杂性新结果：为多个图类提供了新的复杂性分类，包括：
    • 线图的多重图和二部多重图版本
    • KkK_k-free完美图
    • {I4,P4}\{I_4,P_4\}-free图等
  3. 开放问题解决：解决了Alvarado等人(2019)提出的关于{I4,P4}\{I_4,P_4\}-free图夹心问题的开放问题
  4. 非二分性结果：构造了coNP-intermediate的图夹心问题，证明了复杂性分类的非平凡性

方法详解

任务定义

图夹心问题(SP)：给定图类C\mathcal{C}和输入(V,E1,E2)(V,E_1,E_2)其中E1⊆E2E_1 \subseteq E_2，判断是否存在EE使得E1⊆E⊆E2E_1 \subseteq E \subseteq E_2且(V,E)∈C(V,E) \in \mathcal{C}。

等价表述：输入为三元组(V,E,N)(V,E,N)，其中EE为必须边，NN为禁止边，判断是否存在图(V,E′)∈C(V,E') \in \mathcal{C}使得E⊆E′E \subseteq E'且E′∩N=∅E' \cap N = \emptyset。

核心理论框架

2-边着色图与CSP

  • 2-边着色图：三元组(V,B,R)(V,B,R)，其中BB为蓝边集，RR为红边集，且B∩R=∅B \cap R = \emptyset
  • 同态：保持邻接关系和颜色的顶点映射
  • CSP(H)(H)：所有能同态映射到HH的有限2-边着色图构成的类

主要刻画定理

命题3：对于图类C\mathcal{C}，以下等价：

  1. C\mathcal{C}是遗传的、具有联合嵌入性质且在分裂膨胀下封闭
  2. 存在2-边着色图(V,R,B)(V,R,B)使得CSP(V,R,B)=SP(C)(V,R,B) = \text{SP}(\mathcal{C})
  3. 存在图HH使得SP(C)=CSP(H∗)=injCSP(H∗)(\mathcal{C}) = \text{CSP}(H^*) = \text{injCSP}(H^*)

其中H∗H^*表示完全2-边着色图，蓝边为E(H)E(H)，红边为N(H)N(H)。

技术创新点

1. 原始正构造(Primitive Positive Constructions)

利用pp-构造建立CSP之间的归约关系，这对应于图论中的gadget归约。

2. 通用图理论

对于遗传图类C\mathcal{C}，如果存在通用图HH（即Age(H)=C(H) = \mathcal{C}），则SP(C)=CSP(H∗)(\mathcal{C}) = \text{CSP}(H^*)。

3. 分裂膨胀封闭性

  • 膨胀：添加twins（相同邻域的顶点）
  • 共膨胀：添加co-twins（除彼此外邻域相同）
  • 分裂膨胀：根据顶点划分(I,C)(I,C)进行膨胀或共膨胀

实验设置

理论验证

本文主要为理论工作，通过以下方式验证方法有效性：

  1. 已知结果重现：用CSP方法重新证明已知的夹心问题复杂性结果
  2. 新结果推导：利用CSP理论工具获得新的复杂性分类
  3. 计算验证：部分有穷结构的多态性通过计算机程序验证

分析工具

  • Datalog程序：求解某些多项式时间可解的CSP
  • MMSNP归约：将无穷域CSP归约到有穷域
  • 代数方法：利用多态性分析CSP复杂性

实验结果

主要复杂性结果

1. 线图相关

  • 定理：多重图线图的夹心问题是NP-complete
  • 定理：二部多重图线图的夹心问题是NP-complete

2. 禁用子图类

  • 推论18：对于k≥4k \geq 4，{P4,Kk}\{P_4,K_k\}-free图、{P4,Ik}\{P_4,I_k\}-free图和KkK_k-free完美图的夹心问题均为NP-complete
  • 定理17：设FF为非完全点确定图集且FF-free图均为完美图，则对k≥4k \geq 4，(F∪{Kk})(F \cup \{K_k\})-free图的夹心问题为NP-hard

3. 路径禁用

  • 定理20：对于n,k≥4n,k \geq 4，{Pn,Kk}\{P_n,K_k\}-free图的夹心问题为NP-complete

算法复杂性分类

多项式时间可解情况

  • 分裂图：通过2-SAT归约
  • 阈值图：利用完全对称多态性
  • 完全多部图：Datalog程序求解

NP-complete情况

  • 比较图：通过随机偏序的CSP归约
  • 置换图：通过betweenness问题归约
  • 广义分裂图：(p,q)(p,q)-分裂图当p+q>2p+q > 2时

非二分性结果

定理21：如果P ≠\neq coNP，则存在图类C\mathcal{C}使得SP(C)(\mathcal{C})为coNP-intermediate。

构造基于Ladner定理的适配，证明了图夹心问题的复杂性超越了P vs NP二分法。

相关工作

图夹心问题研究

  • Golumbic等(1995)：首次系统研究图夹心问题
  • 后续工作：针对特定图类的复杂性分类
  • 开放问题：完美图夹心问题复杂性未定

约束满足理论

  • Schaefer定理：布尔域CSP的二分法
  • Hell-Nešetřil定理：图同态问题分类
  • 有穷域二分法：Bulatov和Zhuk的突破性结果
  • 无穷域CSP：时序CSP等特殊情况的分类

技术联系

本文首次建立了图夹心问题与无穷域CSP之间的系统联系，为两个领域的交叉提供了新视角。

结论与讨论

主要结论

  1. 理论统一：图夹心问题可以系统地用CSP理论分析
  2. 方法有效：CSP工具能简化复杂性证明并发现新结果
  3. 复杂性丰富：夹心问题展现了从P到coNP-intermediate的完整复杂性谱

局限性

  1. 适用范围：只适用于满足特定条件（遗传、JEP、分裂膨胀封闭）的图类
  2. 完美图问题：最重要的开放问题（完美图夹心问题）仍未解决
  3. 构造性：某些存在性结果缺乏有效的构造算法

未来方向

  1. ω-分类结构：研究ω-分类图类的夹心问题
  2. 完美图问题：寻找完美图夹心问题的解决方案
  3. 可判定性：研究给定禁用子图集合时复杂性的可判定性
  4. NP-intermediate：寻找NP-intermediate的图夹心问题

深度评价

优点

  1. 理论创新：首次建立图夹心问题与CSP理论的系统联系，提供了统一的分析框架
  2. 方法优雅：利用pp-构造等CSP工具大大简化了复杂性证明
  3. 结果丰富：解决了多个开放问题，提供了大量新的复杂性结果
  4. 技术深度：结合了图论、模型论、计算复杂性等多个领域的深刻理论

不足

  1. 适用限制：框架只适用于特定类型的图类，不是完全通用的
  2. 实用性：主要为理论贡献，实际算法改进有限
  3. 完美图：核心开放问题仍未解决

影响力

  1. 学术价值：为图夹心问题研究提供了新的理论工具和视角
  2. 交叉意义：促进了图论与CSP理论的交叉融合
  3. 方法论贡献：pp-构造在图论复杂性分析中的应用具有示范意义

适用场景

该方法特别适用于：

  1. 具有良好结构性质的遗传图类
  2. 存在通用图的图类
  3. 需要系统性复杂性分析的图论问题

参考文献

论文引用了61篇相关文献，主要包括：

  • 图夹心问题的奠基性工作38
  • CSP理论的核心结果20,59,60
  • 无穷域CSP的分类结果10,11,46
  • 图论中的结构性结果22,23,37,47

总结：本文通过建立图夹心问题与约束满足问题之间的深刻联系，为这一经典图论问题提供了全新的理论分析框架。虽然在完全解决所有夹心问题方面仍有局限，但其理论贡献和方法论创新为相关研究开辟了新的道路。