17
$\begingroup$

I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it too abstract. I would be thankful if anybody can suggest me some references of expository nature. I do not have strong background in group theory, so I would prefer papers which use group theory in a gentle way (my background is in CS).

$\endgroup$
  • 1
    $\begingroup$ I do not have the book (unfortunately), but The Graph Isomorphism Problem: Its Structural Complexity by Johannes Köbler, Uwe Schöning, and Jacobo Torán may contain a proof for the case of bounded degree. You might want to check it. $\endgroup$ – Tsuyoshi Ito Aug 21 '12 at 17:56
  • 2
    $\begingroup$ @TsuyoshiIto: While that's an excellent book that gives a good introduction to GI and to a fair bit of general structural complexity, it does not contain much (if anything) about the bounded degree case. I do not know of a gentle introduction to the bounded degree case, but it is so intimately tied with group theoretic methods that I doubt there is an exposition that uses group theory "only gently" (as requested by the OP). $\endgroup$ – Joshua Grochow Aug 23 '12 at 2:05
  • $\begingroup$ I am keen to give an Overview, I will do that soon! $\endgroup$ – Jim Feb 15 '16 at 16:54
14
$\begingroup$

The algorithm for bounded-degree graph isomorphism is so closely tied to (permutation) group theory that I doubt there is an introduction that uses groups "only gently." However, you might consult Paolo Codenotti's Ph.D. thesis for more complete background. He doesn't cover bounded-degree graph isomorphism exactly, but covers the tools needed for it (and the rest of the thesis is about bounded-rank hypergraphs, extending the best known algorithm for general graph isomorphism to the bounded-rank hypergraph case).

You may also find the book Group-Theoretic Algorithms and Graph Isomorphism useful, as it covers most of the background necessary (Chapter 2, "Basic Concepts", is 47 pages) and is a much more leisurely exposition than most of the published papers on the topic.

$\endgroup$
1
$\begingroup$

Notation: Let $X = (V,E)$ be graph, $e = (v_1, v_2) $ an edge of $X$. The vertex set $V_k$ be the set of vertices of distance $k$ from $e$, and let $h$ be the height of $X$.

According to definition of $V_k$, $V= V_0 \cup V_1 \dots V_h$ and $V_{(h+1)}= \emptyset$. Let, subset $E_k$ of edges of $X(0 \leq k \leq h)$ is defined as-

$E_k = \{ (u,w) | u \in V_k, w \in V_ k \cup V_{(k+1)} \}.$

The subgraph $X_i$ is defined as-

$X_k= (V_0 \cup V_1 \dots \cup V_k, E_0 \cup E_1 \dots E_{(k-1)} \}$

For example, $X_2 =\{ (V_0 \cup V_1 \cup V_2, E_0 \cup E_1)\}$

$Aut_e(X)$ is the automorphism group of graph $X$ where $e$ is fixed. If $B$ is a generating set of $Aut_e(X_k)$ , we write $\langle B \rangle = Aut_e(X_k)$, for example, it is clear that $Aut_e(X_0)=\langle(v_1,v_2)\rangle$ where $ (v_1,v_2)$ is a permutation of vertices $v_1, v_2$ of $X$.

Principle Constructing generating set of automorphism group of $X$ is a GI (graph isomorphism) complete problem [1]. So, if we can compute generating set of automorphism group of $X$ (which has bounded valance in polynomial time), we can solve GI in polynomial time. So, we wish to determine $Aut_e(X)$.

Technique:

We will construct $X_0, X_1..... X_h$. For each, $X_k$ we will construct $Aut_e(X_{(k)})$

Note that, a permutation of $Aut_e(X_{(k) })$may be extended to an automorphism of $Aut_e(X_{(k+1)})$.

So, generators of $Aut_e(X_{(k+1)})$ can be obtained from generators for $Aut_e(X_{k})$.

To construct generator, structure-type of $E_k$ is manipulated. The structure-type of $E_k$ can be divided into finite classes. For example, in the trivalent case, there are only six type (only five of those cases can actually occur).

We will classify the edges in $E_k$ into types and will group them into families . This helps to create a number of unique labels.

For a fixed valence, the number of labels is small. At this point, we use the concept of setwise-stabilizers to find permutations which acts on particular label. In the process, we find the generator of $Aut_e(X_{(k) })$. Then, we use the generator of$Aut_e(X_{(k) })$ to find the generator of $Aut_e(X_{(k+1) })$, as stated earlier. Proceeding in this manner, we obtain, $Aut_e(X)$ .

$\endgroup$
  • $\begingroup$ [1]Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132. $\endgroup$ – Jim Jun 1 '16 at 18:35

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.