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

グラフサンドイッチ問題へのCSPアプローチ

基本情報

論文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)はグラフ理論における重要な計算問題である。グラフクラス $\mathcal{C}$ に対して、そのサンドイッチ問題は以下のように定義される：2つのグラフ $(V,E_1)$ と $(V,E_2)$ が与えられ、 $E_1 \subseteq E_2$ であるとき、 $E_1 \subseteq E \subseteq E_2$ を満たし、グラフ $(V,E)$ が $\mathcal{C}$ に属するような辺集合 $E$ が存在するかを判定する問題である。本論文は、多くのサンドイッチ問題が無限2-辺彩色グラフ $H$ の制約充足問題(CSP)と等価であることを証明し、CSP理論を利用して複数のグラフクラスのサンドイッチ問題に対する新しい複雑性結果を提供する。対象となるグラフクラスには、多重グラフの線グラフ、二部多重グラフの線グラフ、 $K_k$ -free完全グラフなどが含まれ、Alvarado等(2019)によって提起された開放問題を解決している。

研究背景と動機

問題の重要性

理論的意義：グラフサンドイッチ問題はグラフ理論における古典的問題であり、Golumbic等により1995年に導入され、グラフ認識問題の自然な拡張である
計算複雑性：サンドイッチ問題は対応するグラフ認識問題と同程度以上に困難であり、その複雑性分類はアルゴリズムグラフ理論における重要な課題である
開放問題：完全グラフのサンドイッチ問題の複雑性はいまだ未決定であり、この分野における最も重要な開放問題の一つと考えられている

既存手法の限界

統一的枠組みの欠如：既存研究は特定のグラフクラスに対する専門的技法を採用することが多く、汎用的な分析方法が不足している
証明の複雑性：従来の硬度証明は通常、複雑なリダクション構成を必要とする
理論的ツールの限定：サンドイッチ問題の複雑性を分析するための体系的な理論的ツールが不足している

研究の動機

本論文は、グラフサンドイッチ問題と制約充足問題の間に関連性を確立し、CSP理論の成熟したツールを利用してサンドイッチ問題に対する統一的な分析枠組みを提供することを目指している。

核心的貢献

理論的枠組みの構築：特定の条件を満たすグラフクラスのサンドイッチ問題が2-辺彩色グラフのCSPと等価であることを証明した
複雑性の新しい結果：複数のグラフクラスに対する新しい複雑性分類を提供する。以下が含まれる：
- 多重グラフおよび二部多重グラフの線グラフ版
- $K_k$ -free完全グラフ
- $\{I_4,P_4\}$ -free グラフなど
開放問題の解決：Alvarado等(2019)によって提起された $\{I_4,P_4\}$ -free グラフのサンドイッチ問題に関する開放問題を解決した
非二分性結果：coNP-intermediateなグラフサンドイッチ問題を構成し、複雑性分類の非自明性を証明した

方法の詳細

タスク定義

グラフサンドイッチ問題(SP)：グラフクラス $\mathcal{C}$ と入力 $(V,E_1,E_2)$ （ $E_1 \subseteq E_2$ ）が与えられたとき、 $E_1 \subseteq E \subseteq E_2$ を満たし、 $(V,E) \in \mathcal{C}$ であるような $E$ が存在するかを判定する。

等価表現：入力は三つ組 $(V,E,N)$ であり、ここで $E$ は必須辺、 $N$ は禁止辺である。グラフ $(V,E') \in \mathcal{C}$ が存在して、 $E \subseteq E'$ かつ $E' \cap N = \emptyset$ を満たすかを判定する。

核心的理論的枠組み

2-辺彩色グラフとCSP

2-辺彩色グラフ：三つ組 $(V,B,R)$ 。ここで $B$ は青辺の集合、 $R$ は赤辺の集合であり、 $B \cap R = \emptyset$ である
準同型：隣接関係と色を保つ頂点写像
CSP $(H)$ ： $H$ に準同型写像可能なすべての有限2-辺彩色グラフの類

主要な特性定理

命題3：グラフクラス $\mathcal{C}$ に対して、以下は等価である：

$\mathcal{C}$ は遺伝的であり、結合埋め込み性質を持ち、分割膨張の下で閉じている
2-辺彩色グラフ $(V,R,B)$ が存在して、CSP $(V,R,B) = \text{SP}(\mathcal{C})$
グラフ $H$ が存在して、SP $(\mathcal{C}) = \text{CSP}(H^*) = \text{injCSP}(H^*)$

ここで $H^*$ は完全2-辺彩色グラフを表し、青辺は $E(H)$ 、赤辺は $N(H)$ である。

技術的革新点

1. 原始正構成(Primitive Positive Constructions)

pp-構成を利用してCSP間のリダクション関係を確立する。これはグラフ理論のgadgetリダクションに対応する。

2. 通用グラフ理論

遺伝的グラフクラス $\mathcal{C}$ に対して、通用グラフ $H$ （すなわちAge $(H) = \mathcal{C}$ ）が存在する場合、SP $(\mathcal{C}) = \text{CSP}(H^*)$ である。

3. 分割膨張閉包性

膨張：同じ近傍を持つ頂点(twins)を追加する
共膨張：互いを除いて同じ近傍を持つ頂点(co-twins)を追加する
分割膨張：頂点分割 $(I,C)$ に基づいて膨張または共膨張を実行する

実験設定

理論的検証

本論文は主に理論的研究であり、以下の方法で方法の有効性を検証している：

既知結果の再現：CSP方法を用いて既知のサンドイッチ問題の複雑性結果を再証明する
新しい結果の導出：CSP理論のツールを利用して新しい複雑性分類を得る
計算による検証：有限構造の多態性の一部はコンピュータプログラムで検証される

分析ツール

Datalogプログラム：多項式時間で解ける特定のCSPを求解する
MMSNPリダクション：無限領域CSPを有限領域に帰約する
代数的方法：多態性を利用してCSP複雑性を分析する

実験結果

主要な複雑性結果

1. 線グラフ関連

定理：多重グラフの線グラフのサンドイッチ問題はNP-完全である
定理：二部多重グラフの線グラフのサンドイッチ問題はNP-完全である

2. 禁止部分グラフクラス

系18： $k \geq 4$ に対して、 $\{P_4,K_k\}$ -free グラフ、 $\{P_4,I_k\}$ -free グラフ、および $K_k$ -free完全グラフのサンドイッチ問題はすべてNP-完全である
定理17： $F$ を非完全点決定グラフの集合とし、 $F$ -free グラフがすべて完全であるとする。 $k \geq 4$ に対して、 $(F \cup \{K_k\})$ -free グラフのサンドイッチ問題はNP-困難である