Difficulty: Intermediate to Advanced | Prerequisites: basic graph theory (vertices, edges, adjacency), probability fundamentals, NP-completeness awareness
Big Picture
Interactive proofs are a model of computation where a powerful prover tries to convince a sceptical verifier that a statement is true, through a back-and-forth exchange of messages. The verifier is computationally limited but can flip coins; the prover is unbounded. This homework explores a concrete interactive proof for Independent Set, a classic NP-complete problem, using a zero-knowledge-style protocol. Graph isomorphism, which asks whether two graphs are structurally identical up to vertex relabelling, shows up both as a tool in the protocol and as its own problem. You should be comfortable with what an independent set is, what graph isomorphism means, and basic probability before working through this material.
TL;DR
The Merlin-Arthur protocol lets a prover (Merlin) convince a verifier (Arthur) that a graph has an independent set of size k, without revealing the set itself. A cheating Merlin can fool Arthur in a single round with probability at most 1/2, so after k rounds the cheat probability drops to at most 1/2^k. Graph isomorphism is tested by checking structural invariants like degree sequences and cycle structures.
Interactive Proof
A proof system involving a prover P and a verifier V who exchange messages over multiple rounds. V is a probabilistic polynomial-time machine; P is computationally unbounded. The system must satisfy completeness (an honest prover always convinces V) and soundness (a cheating prover fools V with only negligible probability).
Think of it as a cross-examination: the verifier keeps asking tricky questions, and only someone who really knows the answer can survive every round.
Prover (Merlin) and Verifier (Arthur)
The standard names for the two parties in an interactive proof. Merlin is all-powerful but not necessarily honest. Arthur is computationally limited but has access to randomness.
Independent Set
A subset I of vertices in a graph G = (V, E) such that no two vertices in I are connected by an edge. Finding a maximum independent set is NP-hard.
In simple terms, a group of vertices that are all strangers to each other, with no direct connections between any pair.
Graph Isomorphism
Two graphs G_1 = (V_1, E_1) and G_2 = (V_2, E_2) are isomorphic if there exists a bijection pi: V_1 -> V_2 such that (u, v) is an edge in E_1 if and only if (pi(u), pi(v)) is an edge in E_2. Informally, the graphs have the same structure but possibly different vertex labels.
Think of it as two maps of the same city drawn with different street names. The layout is identical; only the labels differ.
Permutation (of Vertices)
A bijective mapping pi from the vertex set to itself (or to another set of the same size). Used in the protocol to create isomorphic copies of a graph without revealing the original labelling.
Zero-Knowledge (Informal)
A proof is zero-knowledge if the verifier learns nothing beyond the truth of the statement. In the HW 12 protocol, Arthur becomes convinced that an independent set of size k exists but never learns which vertices are in it.
Soundness
The property that a cheating prover can fool the verifier with at most a small probability. In this protocol, soundness error per round is 1/2.
Completeness
The property that an honest prover always convinces the verifier. If Merlin genuinely has the independent set, Arthur will accept with probability 1 in every round.
Step i) Merlin commits. Merlin picks a random permutation pi of the vertices {1, ..., |V|}. He computes G' = pi(G), the isomorphic copy of G under pi. He sends G' to Arthur in a "locked box" (a commitment he cannot change later).
Step ii) Arthur challenges. Arthur flips a fair coin: b = 0 or b = 1, each with probability 1/2. He tells Merlin the result.
Step iii) Merlin responds.
If b = 0: Merlin sends pi, opens the box, and reveals all of G'. Arthur checks that pi(G) = G'. This verifies that G' is a genuine isomorphic copy of G.
If b = 1: Merlin computes pi(I), opens the box, and reveals only the vertices in pi(I). Arthur checks that pi(I) is an independent set of size k in G'. This verifies the existence of a k-sized independent set in G' (and therefore in G, since G and G' are isomorphic).
They repeat this for k rounds.
If Merlin does not have the independent set, he faces a dilemma. He must commit to G' before learning b, but:
To survive b = 0: G' must be a genuine isomorphism of G. Merlin must know pi and be able to show pi(G) = G'.
To survive b = 1: G' must contain an independent set of size k that Merlin can reveal. But if G has no independent set of size k (or Merlin does not know one), he cannot produce one in a graph isomorphic to G either.
A cheating Merlin's options:
Option A: Send a genuine G' = pi(G). This passes b = 0 but fails b = 1 (he has no independent set to reveal).
Option B: Fabricate a G' that is not isomorphic to G but does contain an independent set of size k. This passes b = 1 but fails b = 0 (Arthur will see that pi(G) ≠ G').
Arthur cannot solve graph non-isomorphism himself, so a fake G' will go undetected if b = 1. But Merlin must commit before seeing b.
In each round, a cheating Merlin must guess b before it is revealed. He has no information about the coin flip, so his probability of guessing correctly is exactly 1/2.
Probability of fooling Arthur in one round: at most 1/2
Probability of fooling Arthur in k rounds: at most (1/2)^k, since the rounds are independent
How many rounds for 99.99% confidence?
Arthur wants the probability that Merlin is cheating and succeeds to be at most 0.0001 = 1/10000.
(1/2)^k ≤ 1/10000
Taking logs: k ≥ log_2(10000) ≈ 13.29
So k = 14 rounds suffice for Arthur to be at least 99.99% confident.
Interactive proofs underpin zero-knowledge proof systems used in blockchain privacy (e.g., zk-SNARKs in Zcash), identity verification without revealing credentials, and secure auctions where bids are verified without being disclosed.
Two graphs are isomorphic if one can be relabelled to become the other. To prove isomorphism, you must exhibit a bijection pi between vertex sets that preserves all edges. To disprove it, you find a structural invariant that differs.
Same number of vertices and edges. If |V_1| ≠ |V_2| or |E_1| ≠ |E_2|, the graphs are not isomorphic.
Same degree sequence. Sort the vertex degrees in non-decreasing order. If the sequences differ, the graphs are not isomorphic.
Same number of cycles of each length. If one graph has a triangle and the other does not, they are not isomorphic.
Same connectivity structure. If one is connected and the other is not, they are not isomorphic.
Passing all these tests does not guarantee isomorphism (they are necessary but not sufficient). You still need to construct the explicit mapping.
To show G_1 is isomorphic to G_2:
Match vertices of the same degree.
Check that adjacency relationships are preserved under the proposed mapping.
Verify that every edge in G_1 maps to an edge in G_2 and vice versa.
All three graphs have 9 vertices. The task is to determine which pairs are isomorphic.
Strategy for solving:
Compute the degree sequence for each graph.
Count edges, triangles, and other small substructures.
For graphs with matching invariants, attempt to construct an explicit vertex bijection.
For graphs with differing invariants, state the invariant that distinguishes them.
When graphs share the same degree sequence, look at the neighbourhood structure: do the degree-3 vertices in one graph connect to the same pattern of degree-3 and degree-2 vertices as in the other? Mismatches in the neighbourhood pattern disprove isomorphism even when the global degree sequence matches.
Students often think that matching degree sequences proves isomorphism. It does not. Two non-isomorphic graphs can have identical degree sequences. You must also verify the adjacency structure.
Students sometimes believe Merlin can cheat by preparing a response for both b = 0 and b = 1 simultaneously. He cannot: the locked box commits him to a single G' before he learns b. He must choose one strategy and hope Arthur's coin lands in his favour.
Students confuse "independent set" with "vertex cover." An independent set has no edges between its members. A vertex cover touches every edge. They are complements: I is an independent set if and only if V \ I is a vertex cover.
Students occasionally forget that the probability analysis requires independence across rounds. Each round uses a fresh permutation and a fresh coin flip, so the rounds are indeed independent.
⚠️ Be ready to explain why a cheating Merlin can survive at most one of the two challenges (b = 0 or b = 1) with a single committed G'. This is the heart of the soundness argument.
⚠️ The round-count calculation ((1/2)^k ≤ epsilon, solve for k) is a standard exam question. Know how to do it cleanly.
⚠️ For graph isomorphism, always start by comparing vertex count, edge count, and degree sequence before attempting a bijection. State the invariant that differs if the graphs are not isomorphic.
⚠️ The protocol is zero-knowledge because Arthur never sees the independent set I directly, only its image pi(I) under a random permutation in a random isomorphic copy. Since pi is fresh each round and unknown to Arthur, pi(I) tells him nothing about I's identity.
True or False: If Merlin has the independent set, Arthur rejects with probability 0 in each round. True (completeness).
Fill in the blank: A cheating Merlin's probability of surviving k rounds is at most ______. (1/2)^k.
True or False: Two graphs with the same degree sequence must be isomorphic. False.
Fill in the blank: To be 99.99% confident, Arthur needs at least ______ rounds. 14.
True or False: In the protocol, Arthur learns which specific vertices form the independent set in G. False. He only sees pi(I) in G', which reveals nothing about I in G.
Q: Why can a cheating Merlin not prepare for both b = 0 and b = 1?
A: He must commit to G' before learning b. If G' = pi(G) (genuine isomorphism), he can handle b = 0 but has no independent set for b = 1. If G' is fabricated with an independent set, he can handle b = 1 but cannot show a valid isomorphism for b = 0. He can only prepare for one.
Q: What happens if Arthur plays 20 rounds and Merlin passes all of them?
A: The probability that a cheating Merlin survives all 20 rounds is at most (1/2)^20 ≈ 0.000001. Arthur can be more than 99.9999% confident that Merlin truly has the independent set.
Q: Describe a necessary condition for two graphs to be isomorphic that is not sufficient.
A: Having the same degree sequence is necessary (an isomorphism preserves vertex degrees) but not sufficient. There exist pairs of non-isomorphic graphs with identical degree sequences, such as certain pairs of 4-regular graphs on the same number of vertices.
Q: In the protocol, what prevents Arthur from learning the independent set I?
A: Arthur only ever sees pi(I), where pi is a random permutation chosen by Merlin. Since pi is uniformly random and independent of previous rounds, the set pi(I) is a random k-subset of G' that reveals no information about the labelling of I in the original graph G.
Q: Suppose two 9-vertex graphs have degree sequences [2, 2, 2, 3, 3, 3, 3, 4, 4]. Are they necessarily isomorphic?
A: No. The degree sequence matching is necessary but not sufficient. You must check adjacency: whether the degree-3 vertices connect to the same pattern of degree-2 and degree-4 vertices in both graphs. A mismatch in these connections disproves isomorphism.
Interactive proofs connect to the complexity class IP, which by the Shamir-Lund-Fortnow-Karloff result equals PSPACE. This is one of the landmark results in computational complexity.
Graph isomorphism connects to secret sharing (Problem 1 in this homework): the protocol uses isomorphic copies to hide information, much as secret sharing uses randomness to hide the secret.
The zero-knowledge property anticipates more advanced topics in cryptography, including zk-SNARKs, commitment schemes, and multi-party computation.
Related Terms / Search Tags
Interactive proof, Merlin-Arthur protocol, zero-knowledge proof, independent set, graph isomorphism, NP-complete, soundness, completeness, permutation, vertex cover, degree sequence, graph invariant, IP = PSPACE, commitment scheme, EECS 376, Foundations of Computer Science, University of Michigan