Computational Complexity of Graph Problems — Mathematics Knowledge System

Overview

Graphs are one of the richest testing grounds for complexity theory: superficially similar problems on the same graph can land on opposite sides of the P vs NP divide. Finding a shortest path or a minimum spanning tree is solvable in polynomial time by well-known efficient algorithms (Dijkstra's, Kruskal's/Prim's), while finding a Hamiltonian cycle, a maximum clique, or an optimal graph coloring is NP-complete, believed to have no polynomial-time exact algorithm. Studying WHY some graph problems are easy and others are hard — and how small changes to a problem's definition can flip it from one class to the other — is a central case study in complexity theory, and directly informs which real-world network, scheduling, and routing problems can be solved exactly versus which require heuristics or approximation.

Intuition

Picture a road network. Asking 'what is the shortest route from A to B?' is easy — an algorithm can greedily expand outward from A, always locking in the next-closest unvisited city, and it never needs to backtrack (Dijkstra's algorithm). But asking 'is there a route that visits every city exactly once and returns home?' (a Hamiltonian cycle, closely related to the Traveling Salesman Problem) has no known such greedy shortcut: committing to visit one city early can make it impossible to reach another later, and there's no known way to detect this without, in the worst case, trying exponentially many orderings. The structural difference — local, incremental decisions that provably stay optimal (shortest path) versus global, all-or-nothing commitments that can only be checked after the fact (Hamiltonian cycle) — is exactly the difference between P and NP-complete showing up inside one subject.

Formal Definition

Definition

Representative graph problems on both sides of the divide, stated as decision problems on a graph G = (V, E):

\text{ShortestPath}(G, s, t, k) = \{\, G : \exists \text{ path } s \to t \text{ of length} \le k \,\} \in P

Shortest path — solvable in P (Dijkstra/BFS)

\text{MST}(G, k) = \{\, G : \exists \text{ spanning tree of weight} \le k \,\} \in P

Minimum spanning tree — solvable in P (Kruskal/Prim)

\text{HamCycle}(G) = \{\, G : \exists \text{ a cycle visiting every vertex exactly once} \,\} \in \text{NP-complete}

Hamiltonian cycle — NP-complete

\text{Clique}(G, k) = \{\, G : \exists \text{ a fully-connected subgraph on } k \text{ vertices} \,\} \in \text{NP-complete}

Clique — NP-complete

\text{Coloring}(G, k) = \{\, G : \text{vertices can be colored with } k \text{ colors, no two adjacent vertices sharing a color} \,\}

In P for k ≤ 2 (bipartiteness test); NP-complete for k ≥ 3

Notation

Notation	Meaning
$G = (V, E)$	A graph with vertex set V and edge set E
$\chi(G)$	The chromatic number of G — the minimum colors needed to properly color it

Theorems

Theorem 1: Dijkstra's algorithm complexity

\text{Single-source shortest paths in a graph with non-negative weights can be computed in } O((|V| + |E|)\log |V|) \text{ time.}

Theorem 2: Karp's Hamiltonian cycle NP-completeness

\text{HamCycle} \text{ is NP-complete: it is in NP, and 3-SAT (or vertex cover) reduces to it in polynomial time.}

Theorem 3: 2-coloring (bipartiteness) is in P; 3-coloring is NP-complete

\text{Deciding if } \chi(G) \le 2 \text{ takes } O(|V|+|E|) \text{ time (BFS/DFS parity check); deciding if } \chi(G) \le 3 \text{ is NP-complete.}

Applications

Network routing protocols rely on Dijkstra's or Bellman-Ford's polynomial-time shortest-path algorithms to compute efficient routes in real time across large networks.

Worked Examples

2-coloring can be tested by picking any vertex, coloring it color 1, then coloring every neighbor the opposite color, and checking for a conflict — a single BFS/DFS pass, no backtracking ever needed because each vertex's color is forced by its distance parity from the start.
$\text{color}(v) = \text{parity of dist}(s, v) \implies O(|V|+|E|) \text{ single-pass test}$
With 3 colors, a vertex's color is no longer forced by one neighbor — assigning it color 1 vs. color 2 can each be locally valid but only one choice may lead to a globally consistent coloring elsewhere, requiring potentially exponential backtracking in the worst case.
$\text{3-COLORING} \le_p \text{no known poly algorithm}; \quad \text{NP-complete (Karp, 1972)}$

Answer: 2-coloring has a forced, non-branching structure (parity from a BFS tree) solvable in linear time, while 3-coloring introduces genuine branching choices whose consistency can only be verified globally, which is exactly the signature of NP-completeness — this is why 3-coloring, unlike 2-coloring, is NP-complete.

Practice Problems

Difficulty 6/10

A network engineer needs the shortest path between two routers in a 10,000-node network with non-negative link weights. Is this tractable, and which algorithm applies?

Difficulty 7/10

A scheduling system models exam slots as graph coloring: each course is a vertex, an edge connects two courses sharing a student, and colors represent time slots. Why might finding the minimum number of slots (the chromatic number) be computationally infeasible for a large university, and what's a practical workaround?

Difficulty 6/10

Which of the following graph problems is solvable in polynomial time?

Finding a Hamiltonian cycleFinding a maximum cliqueFinding a minimum spanning tree3-coloring a graph

Common Mistakes

Common Mistake

Assuming all graph problems are NP-hard because some famous ones (Hamiltonian cycle, clique) are.

Many core graph problems — shortest path, minimum spanning tree, bipartiteness testing, maximum matching, connectivity — are solvable in polynomial time. NP-completeness is the exception among widely-used graph problems, not the rule; each problem's complexity must be established individually.

Common Mistake

Believing that because 2-coloring is easy, 3-coloring must also be easy since it 'just adds one more color.'

Adding a third color removes the forced, parity-based structure that makes 2-coloring solvable by a single linear-time pass, introducing genuine combinatorial branching. 3-coloring (and any k ≥ 3) is NP-complete, illustrating how a seemingly small change in problem statement can cross the P/NP-complete boundary.

Quiz

Flashcards

1 / 4

Historical Background

Graph algorithms and their complexity developed together through the 20th century: Dijkstra published his shortest-path algorithm in 1959, and Kruskal's and Prim's minimum-spanning-tree algorithms date to 1956 and 1957 respectively, all running in low-degree polynomial time. In the other direction, Richard Karp's 1972 paper 'Reducibility Among Combinatorial Problems' proved that several fundamental graph problems — Hamiltonian cycle, vertex cover, clique, and graph coloring among them — are NP-complete, using polynomial-time reductions chained back to Cook and Levin's 1971 proof that Boolean satisfiability (SAT) is NP-complete. This sharp split, within the same subject matter of graphs, became one of the clearest illustrations of the P vs NP boundary.

1956
Joseph Kruskal publishes a minimum-spanning-tree algorithm
Joseph Kruskal
1959
Edsger Dijkstra publishes his polynomial-time shortest-path algorithm
Edsger Dijkstra
1971
Cook and Levin establish SAT is NP-complete, providing the seed problem for later reductions
Stephen Cook, Leonid Levin
1972
Richard Karp proves Hamiltonian cycle, clique, vertex cover, and graph coloring are NP-complete
Richard Karp

Summary

Graph problems split sharply across the P vs NP-complete boundary: shortest path, MST, and bipartiteness are in P; Hamiltonian cycle, clique, and k-coloring (k≥3) are NP-complete.
The dividing line is often whether local, incremental decisions (as in Dijkstra's greedy expansion) provably stay optimal, versus needing global, exponential-in-the-worst-case verification.
Karp's 1972 paper established NP-completeness for many canonical graph problems via reductions chained back to Cook-Levin's SAT result.
Real-world systems (routing, scheduling, register allocation) exploit the P-side algorithms directly and fall back on heuristics/approximations for the NP-complete side.

References

WebsiteWikipedia — Karp's 21 NP-complete problems
WebsiteWikipedia — Dijkstra's algorithm
WebsiteWikipedia — Graph coloring