Algorithms / Subgraph Isomorphism
Least You Need to Know: Subgraph Isomorphism, Pattern Graphs, and Clique-Based Hardness
Subgraph Isomorphism asks whether a pattern graph appears inside a larger host graph. The key exam ideas are what the certificate looks like, why the mapping must preserve edges injectively, and how Clique reduces to the problem by using a complete pattern graph.
The least you need to know
- A yes-certificate is usually an injective mapping from pattern vertices to host vertices.
- The mapping must preserve adjacency: edges in the pattern must map to edges in the host.
- Subgraph Isomorphism is in NP because such a mapping can be checked in polynomial time.
- Clique reduces to Subgraph Isomorphism by using the complete graph `K_k` as the pattern.
- The host graph may contain extra vertices and edges; only the embedded pattern matters.
Key notation
H -> G
map vertices of pattern graph `H` into host graph `G`
injective
distinct pattern vertices map to distinct host vertices
K_k
complete graph on `k` vertices
Tiny worked example
- Suppose the pattern graph is a triangle.
- A certificate chooses three distinct vertices in the host graph.
- Verification checks that all three corresponding host edges are present.
- This is exactly why `Clique` reduces to `Subgraph Isomorphism` when the pattern is `K_k`.
Common mistakes
- Students sometimes forget injectivity and accidentally map two pattern vertices to one host vertex.
- Extra edges in the host do not hurt; the requirement is that pattern edges must exist after mapping.
- The direction from Clique to Subgraph Isomorphism is what proves hardness of the latter.
How to recognize this kind of problem
- The problem asks whether one graph occurs as a pattern inside another.
- A candidate witness is an explicit vertex mapping.
- A hardness proof uses `K_k` or another known hard pattern problem.