Title: A CSP approach to Graph Sandwich Problems Show Chinese title

Title: 一种CSP方法用于图夹逼问题

Abstract: 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). Show Chinese abstract

Abstract: 对于图类$\calC$的\emph{夹层问题}(SP) 是以下计算问题。 输入是一对图$(V,E_1)$和$(V,E_2)$，其中$E_1\subseteq E_2$，任务是判断是否存在边集$E$，使得$E_1\subseteq E \subseteq E_2$，这样图$(V,E)$属于$\calC$。 在本文中，我们表明许多SP对应于无限$2$边色图$H$的约束满足问题（CSP）。我们随后注意到，若干已知的SP复杂性结果也来自于无限域CSP的一般复杂性分类，这表明将CSP理论应用于SP的复杂性分类具有良好的前景。我们通过使用约束满足理论的基本工具，提出了一些图类的SP的新复杂性结果，包括多重图的线图、二分多重图的线图、$K_k$-自由完美图以及通过禁止有限多个诱导子图描述的类，例如$\{I_4,P_4\}$-自由图，解决了Alvarado、Dantas和Rautenbach（2019）提出的一个开放问题。我们还构造了一个图夹逼问题，该问题属于coNP，但既不属于P也不属于coNP完全（除非P=coNP）。