2
$\begingroup$

Suppose you are given two graphs with $v$ vertices and wish to check whether they are isomorphic are not. One possible way to do this is to enumerate all possible permutations of the $v$ vertices and see if any of these permutations create a bijection between the edges and vertices of the graphs. However, this type of algorithm takes a global view of the problem, I was wondering if there was an algorithm that took a more local view. That is, if you input a graph into this algorithm it will output a specific vertex (up to automorphism of course) regardless of how the vertices are labeled.

If we called the local view algorithm $P(G)$, then the full algorithm to check isomorphism between graphs $G$ and $H$ would work as follows:

$1)$ Run $P(G)$ and $P(H)$

$2)$ Store the vertices outputted as equivalent vertices

$3)$ Remove these vertices from $G$ and $H$. Return to step $1)$

After $v$ steps, you will have a list of $v$ pairs of equivalent vertices. You then check whether this list actually describes an isomorphism between the graphs. If it does, the graphs are isomorphic, if not then they are not.

Such an algorithm $P(G)$ is not computable in polynomial time as the other steps in the algorithm above can be computed in polynomial time. If this were not the case, then graph isomorphism would be computable in polynomial time (this is not currently known). Here is an example for a specific type of graph: Suppose $G$ and $H$ are graphs such that every vertex has a unique degree and every vertex is only connected to itself. Then $P(G)$ simply outputs the vertex with the largest degree.

Reiterating the question: Does such a local algorithm exist for all graphs?

$\endgroup$
3
  • 2
    $\begingroup$ Is this a question? $\endgroup$
    – Magma
    Feb 4 '20 at 23:17
  • $\begingroup$ Yes, does such a local view algorithm exist? $\endgroup$
    – QC_QAOA
    Feb 4 '20 at 23:35
  • $\begingroup$ To be honest I can't actually think of any interesting class of graphs where such an algorithm might exist. Here are some uninteresting classes though: Complete or empty graphs: Pick any vertex. Complete multipartite graphs: Pick any vertex of highest degree (lowest won't work). $\endgroup$
    – Magma
    Feb 4 '20 at 23:45
3
$\begingroup$

The closest you can get to this is to use some sort of Canonical Labeling for your graph (which will put all the vertices into some specified ordering), and then the special vertex you return can be the first vertex according to this labeling. Of course this takes a more global view, because you would just see if $G$ and $H$ look the same under the canonical labeling.

There is no (known) way to do this with a more local view, as you suggest, because you really need to consider all of the vertices in order to decide which "special" vertex to return (if you want this special vertex to be invariant under the isomorphisms of the graph in some way). So of course it is just as complicated to decide a single vertex to choose as the "first" vertex as it will be to decide an ordering for all of the vertices.

For more information about canonical labelings, you can look at some information involved in the nauty package for testing graph isomorphisms.

$\endgroup$
1
  • $\begingroup$ Ah, this is the sort of thing I was looking for $\endgroup$
    – QC_QAOA
    Feb 5 '20 at 0:45
1
$\begingroup$

To formalize this problem, it's probably best to reformulate it in simple terms in the language of graphs:

I'll call a class $C$ of graphs carefully reducible if for any nonzero graph $G$ in $C$ there's a vertex $P(G)$ of $G$ such that $G-P(G)$ is also in $C$ and any isomorphism of $G-P(G)$ extends to an isomorphism of $G$.

Now a class of graphs has a local view algorithm iff it is carefully reducible. The proof of that is straightforward.

Now here's a moderately interesting class of graphs that satisfies this property:

I claim that the class of cographs is carefully reducible.

Cographs are a class of graphs generated recursively from one-vertex graphs by either taking disjoint unions or joins. A cotree is a rooted tree where every non-leaf node is marked either as union or join, and there is a recursively defined map from cotrees to cographs that maps a one-vertex cotree to a one-vertex graph, a union-rooted cotree to the disjoint union of the cographs of its branches, and a join-rooted cotree to the join of the cographs of its branches.

This map induces a canonical correspondence between the leaves of the cotree and the vertices of its cograph. There's an inverse of this map too, which maps each cograph to the unique minimal cotree generating it.

The idea is now to devise a local algorithm as follows For every cograph $G$, we construct its minimal cotree $T$. Then we select a particular leaf $L(T)$ of $T$ using its structure, and let $P(G)$ be the corresponding vertex of $G$.

Here's an algorithm to find $L(T)$ for a given minimal cotree $T$:

  • If $T$ is a one-vertex tree, choose $L(T)$ to be the root.
  • Otherwise, remove the root and order the components (first by number of vertices ascending, and as tiebreaker any fixed complete ordering of cotrees).
  • Call $S$ the first component according to this ordering. Choose $L(T)$ to be $L(S)$.

I'll leave the proof (that this choice of $P$ causes the careful reduction property of cographs to be satisfied) as an exercise to you.

Interestingly, cographs are also characterized by the property of not having a $P_4$ (path on 4 vertices) as an induced subgraph, and indeed any class of graphs that includes the $P_4$ graph is not carefully reducible. However, there are actually carefully reducible graph classes that do contain non-cographs:

enter image description here

Let $G$ be the infinite graph pictured above. Consider the class $C$ of graphs defined as the class of all subgraphs $G_n$ induced from $G$ by the vertices $1 \ldots n$, and let $P(G_n) = n$. Now in this case it is easy to verify that any isomorphism of $G_{n-1}$ extends to an isomorphism of $G_n$. So $C$ is indeed carefully reducible, but $G_n$ is not a cograph for all $n > 5$.

$\endgroup$

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.