4
$\begingroup$

Stefan Kratsch and Pascal Schweitzer in their paper Graph Isomorphism for Graph Classes Characterized by two Forbidden Induced Subgraphs give a characterization of graphs on which Graph Isomorphism is solvable in polynomial time (Theorem 4, page 8).

I have a problem understanding the outline of the proof for Theorem 4 and therefore the proofs of the different cases itself. The main idea is to construct colored graphs of bounded color valence for which the problem is solvable in polynomial time according to Theorem 5.

For creating such graphs one tries to find a canonical coloring. One such method is called individualization.

As this method is just described as:

We guess an ordered set of vertices of constant size, color the vertices in this set with singleton colors, and then color the remaining vertices according to their adjacencies to the vertices in the ordered set.

and not further specified in the following proofs.

I have two questions:

  1. How exactly is this coloring done?
  2. What exactly is a canonical coloring?
$\endgroup$

1 Answer 1

7
$\begingroup$
  1. Typically the way individualization goes is this. You're trying to decide if two vertex-colored graphs $G$ and $H$ are isomorphic in a way that respects the colors (sends vertices of color $c$ in $G$ to those of the same color $c$ in $H$). You pick a vertex $v$ in $G$ and assign it a new color, say $c$, that has not been used before. This is called "individualization." Then for each vertex $w \in V(H)$ you will, in turn, try coloring $w$ with $c$ and see if there is an isomorphism $G \to H$ that respects this new coloring. (This incurs a multiplicative cost of $|V(H)|$, so you don't want to do this too often.) In other words, you are guessing the vertex $v$, and then trying to see which vertices of $H$ it can possibly map to.

To aid in this quest, frequently individualization is followed by a process called (Weisfeiler-Lehman) refinement. What happens here is that you assign new colors to each vertex according to the multi-set of colors of its neighbors. Then you do this again. Then you do this again. And you keep doing this until the partition of vertices by color does not change.

  1. An isomorphism-invariant coloring of graphs is a method of assigning colors to vertices so that if two graphs are isomorphic, then there is an isomorphism between them that sends vertices of color $c$ to vertices of color $c$. Some authors will call this coloring canonical - and indeed, in the paper you cite, it may be that all they need is a canonical coloring in which each color class has bounded size. (Other authors might say that a canonical coloring is an isomorphism-invariant coloring in which each vertex receives a color that is distinct from that of all other vertices. In this way, if we can compute a canonical coloring of two graphs $G,H$, then there is only one possible isomorphism between them (namely, the one that respects the colors), and it is easy to check whether this is actually an isomorphism.)

Combined with individualization, one can talk about a coloring that is canonical relative to the individualizations that have been made previously. That is, it may not be canonical with respect to isomorphisms of the original graphs, but given the vertices that have been colored so far it is canonical. (In this sense individualization is a form of "partial brute-force search," in which you keep track of how the guesses you've made so far constrain your future search.)

$\endgroup$
3
  • $\begingroup$ To create a colored graph of bounded color valence, what we try to achieve: Create a colored graph (that respects isomorphism and doesn't have to be proper) by e.g. like in case 1 individualizing a vertex and showing that its co-degree/degree is bounded (while bounded means that one can't create vertices with arbitrarly large degree/co-degree, even when $V(G)=n\to\infty$). Given these properties one can create a colored graph with bounded color valence by assigning the same color to all neighbors/non-neighbors of the one individualized vertex. Is that the right approach to the problem? $\endgroup$ Jan 14, 2016 at 15:59
  • $\begingroup$ @Heinz-Heinrich: This is roughly the right approach but one must be careful. In order to get all vertices to have bounded color valence, naively following this approach will require individualizing nearly every vertex, which essentially just amounts to brute-force search over all isomorphisms. The multiplicative cost incurred by individualizing a vertex in one graph and then having to pick which vertex in the other graph to individualize can be prohibitive, without more detailed analysis. $\endgroup$ Jan 15, 2016 at 17:32
  • $\begingroup$ @Heinz-Heinrich: Also, individualizing one vertex doesn't merely assign one color to all its neighbors and one color to all its non-neighbors. The first step after individualizing does this. The second step after individualizing refines this coloring further (by, e.g., knowing, for every vertex v, how many neighbors of the individualized vertex was v adjacent to). And so on. Lookup the Weisfeiler-Lehman algorithm. $\endgroup$ Jan 15, 2016 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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