2
$\begingroup$

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing an oracle that solves graph isomorphism for (n-1) vertices.

To be clear, the oracle only tells 'Yes' or 'No'. It does not give us the isomorphism.

This problem appears as an exercise in Arora-Barak's chapter on Interactive Proofs.


How do I show that Graph Isomorphism is downward self-reducible?

My attempt is to start with an arbitrary vertex in $G_1$ and guess its image in $G_2$, and remove them and make an oracle call on the remaining graph. But now, I do not know how to proceed. These graphs being isomorphic may not necessarily mean that the original graphs are isomorphic.

$\endgroup$
  • $\begingroup$ I removed your "NP-complete" tag, since graph isomorphism isn't known to be NP-complete (and seems not to be -- if it were, the polynomial hierarchy would collapse). $\endgroup$ – David Richerby Apr 24 at 13:30
  • $\begingroup$ @Apass.Jack clarfied $\endgroup$ – Agnishom Chattopadhyay Apr 25 at 19:18
  • $\begingroup$ Does the "Chapter on Interactive Proofs" imply probabilistic methods? Although I believe graph isomorphism is deterministic downward self polynomial-time reducible, can you clarify that the definition in the book is indeed having nothing to do randomization or probability? I do not have the book. $\endgroup$ – Apass.Jack May 7 at 4:52
0
$\begingroup$

This answer shows how to prove an easier variation, the case of (undirected loopless) multigraph isomorphism.

The problem of multigraph isomorphism is downward self-reducible

The simple idea is to merge two vertices in a way that distinguish those two vertices and edges involving them.


Let $G$ be a multigraph. If the sum of degrees of two vertices reaches the maximum, we will call an ordered pair of those two vertices a degree-maximum pair. For a degree-maximum pair $(u,v)$, construct $G_{u,v}$ as follows.

  • Its vertices are all vertices of $G$ except $u$ and $v$, together with a new vertex $u_v$ which is understood as $u$ merged by $v$. Note that $G_{u,v}$ has one less vertice than $G$.

  • Its edges consists of two parts.

    • the edges of $G$ whose endpoints are neither $u$ nor $v$ with the same multiplicity. Let $m$ be the maximum multiplicity of these edges.
    • for all vertex $w$ of $G$ that is neither $u$ nor $v$, edge $\{w, u_v\}$ with multiplicity that is the sum of the multiplicity of $\{w,u\}$ in $G$ and the product of $m+1$ and the multiplicity of $\{w,v\}$ in $G$.

It is easy to see that if we are given a multigraph $G'$ that is isomorphic to $G_{u,v}$ for some multigraph $G$, we can reconstruct $G$ from $G'$ up to isomorphism.


Suppose we are given two graphs of $n$ vertices, $G$ and $H$. Use the oracle to compare $G_{u,v}$ with $H_{x,y}$ for all tuples $(u,v,x,y)$, where $(u,v)$ is a degree-maximum pair in $G$ and $(x,y)$ is a degree-maximum pair in $H$. Once the oracle return yes, we conclude $G$ and $H$ are isomorphic; otherwise the oracle always return no, in which case we conclude $G$ and $H$ are not isomorphic. It take polynomial time to construct $G_{u,v}$ from $G$ or $H_{x,y}$ from $H$. There are less than $n^2$ tuples. So the whole algorithm takes polynomial time. QED.


I am yet to find a proof that shows the problem of (non-multi)graph isomorphism is downward self-reducible.

$\endgroup$
  • $\begingroup$ As my effort to simplify is too aggressive, there is a minor/critical flaw in my algorithm above. I should have selected a degree-minimum connected pair $(u,v)$. $\endgroup$ – Apass.Jack Apr 26 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.