A CSP approach to Graph Sandwich Problems

Basic Information

• Paper ID: 2510.09128
• Title: A CSP approach to Graph Sandwich Problems
• Authors: Manuel Bodirsky, Santiago Guzmán-Pro (TU Dresden)
• Classification: cs.DM (Discrete Mathematics), cs.CC (Computational Complexity), math.CO (Combinatorics)
• Publication Date: October 13, 2025
• Paper Link: https://arxiv.org/abs/2510.09128

Abstract

Graph Sandwich Problems (SP) represent an important computational problem in graph theory. For a graph class $\mathcal{C}$, its sandwich problem is defined as follows: given two graphs $(V,E_1)$ and $(V,E_2)$ with $E_1 \subseteq E_2$, determine whether there exists an edge set $E$ such that $E_1 \subseteq E \subseteq E_2$ and the graph $(V,E)$ belongs to $\mathcal{C}$. This paper proves that many sandwich problems are equivalent to constraint satisfaction problems (CSP) of infinite 2-edge-colored graphs $H$, and leverages CSP theory to provide new complexity results for sandwich problems of multiple graph classes, including line graphs of multigraphs, line graphs of bipartite multigraphs, and $K_k$-free perfect graphs, thereby resolving open problems posed by Alvarado et al. (2019).

Research Background and Motivation

Problem Significance

1. Theoretical Importance: Graph sandwich problems are classical problems in graph theory, introduced by Golumbic et al. in 1995, and represent a natural generalization of graph recognition problems
2. Computational Complexity: Sandwich problems are at least as difficult as the corresponding graph recognition problems, and their complexity classification is an important topic in algorithmic graph theory
3. Open Problems: The complexity of sandwich problems for perfect graphs remains undetermined and is considered one of the most important open problems in the field

Limitations of Existing Approaches

1. Lack of Unified Framework: Existing research predominantly employs specialized techniques for specific graph classes, lacking a general analytical method
2. Complex Proofs: Traditional hardness proofs typically require intricate reduction constructions
3. Limited Theoretical Tools: Systematic theoretical tools for analyzing the complexity of sandwich problems are lacking

Research Motivation

This paper aims to establish connections between graph sandwich problems and constraint satisfaction problems, utilizing mature CSP theory tools to provide a unified analytical framework for sandwich problems.

Core Contributions

1. Theoretical Framework Establishment: Proves that sandwich problems of graph classes satisfying specific conditions are equivalent to CSPs of 2-edge-colored graphs
2. New Complexity Results: Provides new complexity classifications for multiple graph classes, including:
   • Line graphs of multigraphs and bipartite multigraphs
   • $K_k$-free perfect graphs
   • $\{I_4,P_4\}$-free graphs, etc.
3. Resolution of Open Problems: Resolves the open problem posed by Alvarado et al. (2019) regarding sandwich problems of $\{I_4,P_4\}$-free graphs
4. Non-Dichotomy Results: Constructs graph sandwich problems that are coNP-intermediate, proving the non-triviality of complexity classification

Methodology Details

Problem Definition

Graph Sandwich Problem (SP): Given a graph class $\mathcal{C}$ and input $(V,E_1,E_2)$ where $E_1 \subseteq E_2$, determine whether there exists $E$ such that $E_1 \subseteq E \subseteq E_2$ and $(V,E) \in \mathcal{C}$.

Equivalent Formulation: Input is a triple $(V,E,N)$, where $E$ is the set of required edges and $N$ is the set of forbidden edges. Determine whether there exists a graph $(V,E') \in \mathcal{C}$ such that $E \subseteq E'$ and $E' \cap N = \emptyset$.

Core Theoretical Framework

2-Edge-Colored Graphs and CSP

• 2-Edge-Colored Graph: A triple $(V,B,R)$, where $B$ is the set of blue edges and $R$ is the set of red edges, with $B \cap R = \emptyset$
• Homomorphism: A vertex mapping that preserves adjacency relationships and colors
• CSP$(H)$: The class of all finite 2-edge-colored graphs that can be homomorphically mapped to $H$

Main Characterization Theorem

Proposition 3: For a graph class $\mathcal{C}$, the following are equivalent:

1. $\mathcal{C}$ is hereditary, possesses the joint embedding property, and is closed under split-extension
2. There exists a 2-edge-colored graph $(V,R,B)$ such that CSP$(V,R,B) = \text{SP}(\mathcal{C})$
3. There exists a graph $H$ such that SP$(\mathcal{C}) = \text{CSP}(H^*) = \text{injCSP}(H^*)$

where $H^*$ denotes the complete 2-edge-colored graph with blue edges $E(H)$ and red edges $N(H)$.

Technical Innovations

1. Primitive Positive Constructions

Utilizes pp-constructions to establish reduction relationships between CSPs, which correspond to gadget reductions in graph theory.

2. Universal Graph Theory

For a hereditary graph class $\mathcal{C}$, if there exists a universal graph $H$ (i.e., Age$(H) = \mathcal{C}$), then SP$(\mathcal{C}) = \text{CSP}(H^*)$.

3. Split-Extension Closure

• Extension: Adding twins (vertices with identical neighborhoods)
• Co-extension: Adding co-twins (vertices with identical neighborhoods except each other)
• Split-Extension: Performing extension or co-extension according to vertex partition $(I,C)$

Experimental Setup

Theoretical Verification

This paper is primarily theoretical work, with validity verified through:

1. Reproduction of Known Results: Re-proving known complexity results for sandwich problems using the CSP method
2. Derivation of New Results: Obtaining new complexity classifications using CSP theory tools
3. Computational Verification: Polymorphisms of certain finite structures verified through computer programs

Analysis Tools

• Datalog Programs: Solving certain polynomial-time solvable CSPs
• MMSNP Reductions: Reducing infinite-domain CSPs to finite-domain ones
• Algebraic Methods: Analyzing CSP complexity using polymorphisms

Experimental Results

Main Complexity Results

1. Line Graph Related

• Theorem: The sandwich problem for line graphs of multigraphs is NP-complete
• Theorem: The sandwich problem for line graphs of bipartite multigraphs is NP-complete

2. Forbidden Subgraph Classes

• Corollary 18: For $k \geq 4$, the sandwich problems for $\{P_4,K_k\}$-free graphs, $\{P_4,I_k\}$-free graphs, and $K_k$-free perfect graphs are all NP-complete
• Theorem 17: Let $F$ be a set of non-complete vertex-determining graphs such that $F$-free graphs are perfect. Then for $k \geq 4$, the sandwich problem for $(F \cup \{K_k\})$-free graphs is NP-hard

3. Path Forbidden

• Theorem 20: For $n,k \geq 4$, the sandwich problem for $\{P_n,K_k\}$-free graphs is NP-complete

Algorithmic Complexity Classification

Polynomial-Time Solvable Cases

• Split graphs: Via 2-SAT reduction
• Threshold graphs: Utilizing complete symmetric polymorphisms
• Complete multipartite graphs: Solved via Datalog programs

NP-Complete Cases

• Comparability graphs: Via CSP reduction of random partial orders
• Permutation graphs: Via betweenness problem reduction
• Generalized split graphs: $(p,q)$-split graphs when $p+q > 2$

Non-Dichotomy Results

Theorem 21: If P $\neq$ coNP, then there exists a graph class $\mathcal{C}$ such that SP$(\mathcal{C})$ is coNP-intermediate.

The construction is based on an adaptation of Ladner's theorem, proving that the complexity of graph sandwich problems transcends the P vs NP dichotomy.

Related Work

Graph Sandwich Problem Research

• Golumbic et al. (1995): First systematic study of graph sandwich problems
• Subsequent Work: Complexity classification for specific graph classes
• Open Problems: Complexity of sandwich problems for perfect graphs remains undetermined

Constraint Satisfaction Theory

• Schaefer's Theorem: Dichotomy for Boolean domain CSPs
• Hell-Nešetřil Theorem: Classification of graph homomorphism problems
• Finite Domain Dichotomy: Breakthrough results by Bulatov and Zhuk
• Infinite Domain CSP: Classification of special cases such as temporal CSPs

Technical Connections

This paper establishes for the first time a systematic connection between graph sandwich problems and infinite-domain CSPs, providing a new perspective for cross-disciplinary research.

Conclusions and Discussion

Main Conclusions

1. Theoretical Unification: Graph sandwich problems can be systematically analyzed using CSP theory
2. Method Effectiveness: CSP tools simplify complexity proofs and enable discovery of new results
3. Complexity Richness: Sandwich problems exhibit a complete complexity spectrum ranging from P to coNP-intermediate

Limitations

1. Scope of Applicability: Only applicable to graph classes satisfying specific conditions (hereditary, JEP, split-extension closed)
2. Perfect Graph Problem: The most important open problem (perfect graph sandwich problem) remains unsolved
3. Constructiveness: Some existence results lack effective constructive algorithms

Future Directions

1. ω-Categorical Structures: Study sandwich problems for ω-categorical graph classes
2. Perfect Graph Problem: Seek solutions to the perfect graph sandwich problem
3. Decidability: Investigate decidability of complexity when given forbidden subgraph sets
4. NP-Intermediate: Search for NP-intermediate graph sandwich problems

In-Depth Evaluation

Strengths

1. Theoretical Innovation: First systematic connection between graph sandwich problems and CSP theory, providing a unified analytical framework
2. Elegant Methodology: Significantly simplifies complexity proofs through pp-constructions and other CSP tools
3. Rich Results: Resolves multiple open problems and provides numerous new complexity results
4. Technical Depth: Combines profound theories from graph theory, model theory, and computational complexity

Weaknesses

1. Application Restrictions: Framework only applies to specific types of graph classes, not completely universal
2. Practical Utility: Primarily theoretical contributions with limited improvements to practical algorithms
3. Perfect Graphs: Core open problem remains unsolved

Impact

1. Academic Value: Provides new theoretical tools and perspectives for graph sandwich problem research
2. Interdisciplinary Significance: Promotes cross-disciplinary integration of graph theory and CSP theory
3. Methodological Contribution: Demonstrates exemplary application of pp-constructions in graph-theoretic complexity analysis

Applicable Scenarios

This method is particularly suitable for:

1. Hereditary graph classes with good structural properties
2. Graph classes with universal graphs
3. Graph-theoretic problems requiring systematic complexity analysis

References

The paper cites 61 related references, primarily including:

• Foundational work on graph sandwich problems 38
• Core CSP theory results 20,59,60
• Classification results for infinite-domain CSPs 10,11,46
• Structural results in graph theory 22,23,37,47

Summary: By establishing profound connections between graph sandwich problems and constraint satisfaction problems, this paper provides a novel theoretical analytical framework for this classical graph-theoretic problem. While limitations remain in completely resolving all sandwich problems, its theoretical contributions and methodological innovations open new avenues for related research.