Modelling Patterns

The hard part of a graph problem is usually noticing it is a graph problem, and choosing the right vertices. This page is a lookup table from problem phrasing to construction.

Recognising the graph

Phrasing	Vertices	Edges
”minimum number of operations to transform X into Y”	states	one operation
”can we reach this configuration”	configurations	one move
”who must come before whom”	items	precedence
”these two cannot both be chosen”	choices	conflict — think 2-SAT or bipartite
”assign each A to a B”	A’s and B’s	compatibility — matching
”minimum cost to separate / block”	as given	min cut
”maximum number of disjoint routes”	as given	max flow
”connect everything cheaply”	as given	MST
”cheapest route”	as given	shortest path

The state-space transformations

Layered graphs — state that travels with you

When movement depends on something you carry, make the vertex a pair.

Carried state	Vertex
Keys collected	$(v,\text{mask})$
Fuel remaining	$(v,f)$
Moves used mod $k$	$(v,t\mathrm{mod}k)$
“Have I used my one free teleport?”	$(v,0/1)$
Which of $k$ discounts remain	$(v,j)$
Current speed / direction	$(v,d)$

The graph grows by a factor equal to the number of states; the algorithm is unchanged.

Node splitting — constraints on vertices

Split $v$ into $v_{in}\to v_{out}$ and put the constraint on the internal edge:

• vertex capacity → capacity on the internal edge;
• vertex cost → cost on the internal edge;
• vertex-disjoint paths → internal capacity 1;
• “visit at most $k$ special cities” → count on the internal edge.

Edge subdivision — costs that depend on usage

Replace an edge by several parallel edges with increasing cost. Because min-cost flow uses the cheapest first, this exactly models a convex piecewise-linear cost.

Reversal — “how many edges must I flip”

Add each edge forward with weight 0 and backward with weight 1, then run 0-1 BFS.

Complement graphs

When the graph is dense but its complement is sparse, run BFS on the complement in $O(V+E)$ total by keeping the unvisited vertices in a set and erasing as you go. This turns “BFS on a graph with $10^{10}$ edges” into something feasible.

set<int> unvisited;                 // all vertices initially
while (!q.empty()) {
    int u = q.front(); q.pop();
    vector<int> toVisit;
    for (int v : unvisited)
        if (!adjSet[u].count(v)) toVisit.push_back(v);   // edge in the complement
    for (int v : toVisit) { unvisited.erase(v); q.push(v); }
}

Reductions worth memorising

Problem	Reduces to
Minimum path cover of a DAG	$V$ − bipartite matching
Maximum independent set, bipartite	$V$ − max matching
Minimum vertex cover, bipartite	max matching (König)
Maximum antichain in a poset	Dilworth → matching
Project selection / maximum closure	min cut
Binary labelling with pairwise penalties	min cut
”Every road at least once”	Chinese postman
$k$ disjoint minimum-cost paths	min-cost flow of value $k$
Difference constraints $x_j-x_i\le c$	Bellman-Ford
Boolean constraints, two literals per clause	2-SAT
Maximise the minimum edge on a path	MST path maximum
Reachability with cycles	condense, then DAG DP
Distance queries between many pairs on a tree	LCA

Sanity checks before coding

1. Directed or undirected? Getting this wrong invalidates everything downstream.
2. Are there self-loops or parallel edges? They break naive parent-skipping and DSU-based cycle checks.
3. Is the graph connected? Many algorithms need a loop over all start vertices.
4. Are weights non-negative? If not, Dijkstra is silently wrong.
5. Does $n$ fit the algorithm? $V^3$ needs $V\le 500$; $2^V$ needs $V\le 22$.
6. Is the answer “impossible”? Decide the sentinel value before writing the loop.

See also: Complexity Cheatsheet · Representations · Problem Pattern Recognition