SOBRE GRAFO SANDUÍCHE

Abstract

This work presents a literature review on the Graph Sandwich Problem, highlighting its formulation, main applications, and behavior in different computational complexity scenarios. First, it addresses the fundamental concepts of Graph Theory, computational complexity, and (k,l)-partition, which occurs when the vertex set can be divided into k independent sets and l cliques, providing the basis for the analysis. Next, five variations of the problem are discussed: split (1,1), bipartite (2,0), partition (2,1), partition (2,2), and (k,l)Δ-limited. The results show that the split (1,1) and bipartite (2,0) variations are solvable in polynomial time. The (2,1) and (2,2) partitions are NP-complete, proven through reductions from 3-SAT. For the (k,l)Δ-limited cases, it was found that the problem is polynomial when k ≤ 2 or Δ ≤ 3, and becomes NP-complete when k ≥ 3 and Δ ≥ 4, demonstrating how the graph structure and maximum degree directly impact complexity. It is concluded that analysis through (k,l)-partition is an effective tool for understanding the boundaries between tractable and intractable cases, in addition to highlighting the theoretical and practical relevance of this problem in different contexts.