0
$\begingroup$

Got an isomorphism preserving transformation to a graph of bounded clique width and rank width. It, a paper and graphclasses.org imply graph isomorphism is in P, so likely something is wrong.

Let $G$ be simple connected graph of order $n$ and $n>2$.

Consider the following isomorphism preserving transformation $G \to G'$.

Initially the vertices of $G'$ are $V_1=V(G) \times V(G)=\{(v_i,v_j)| v_i \in V(G),v_j \in V(G) \}$.

Make a clique of $V_1$.

For all edges $(u,v) \in E(G)$ add vertices $A_{u,v},A_{v,u}$ and call these vertices $A$ vertices. Add edges $(A_{u,v},(u,v))$ and $A_{v,u},(v,u))$.

All $A$ vertices are degree one and are adjacent to exactly one $V_1$ vertex.

In an edge $(A_{u,v},(u,v))$, the $V_1$ vertex $(u,v)$ corresponds to the edge $(u,v)$ in $E(G)$.

Given $G'$, we can recover $G$. Take all neighbors of the degree one $A$ vertices $(u_1,v_1),(v_1,u_1),\ldots (v_n,u_n)$. These are exactly the undirected edges of $G$, where an edge is given as both $(u,v)$ and $(v,u)$.

So $G \cong H \iff G' \cong H'$ and the transformation is isomorphism preserving.

$|V(G')|=n^2+2|E(G)|=O(n^2)$.

According to graphclasses the class $(C_{n+4},gem)$-free is of bounded clique width and bounded rank width. This class are the graphs which don't have induced subgraph "gem" and induced cycle of length at least $4$.

We claim that for all $G$, $G'$ is in this class.

Since the $A$ vertices are of degree one, they can't be in a cycle.

This leaves only the clique $V_1$ and four or more vertices in it induce $K_4$ as subgraph, which kills induced cycles.

The gem graph is on 5 vertices:

gem graph

Since it doesn't have degree one vertex, there are no $A$ vertices and it is not induced subgraph of the clique.

Experiments in Sage suggest both recovering the original graph and $G'$ is in the bounded class.

According to Isomorphism Testing for Graphs of Bounded Rank Width

We give an algorithm that, for every fixed $k$, decides isomorphism of graphs of rank width at most $k$ in polynomial time. As the clique width of a graph is bounded in terms of its rank width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.

So the transformation, the paper and graphclass.org imply graph isomorphism is in P.

What is wrong with the argument that graph isomorphism is in P?

Sage implementation:

def graphtoedgeclique2(g,adc=False):
    """
    graph to edge clique 2
    """
    ve=list(g.vertices())
    E=[]
    l=[]
    for u,v in cartesian_product_iterator([ve]*2):
        l += [(u,v)]
    E += listtoclique(l)    
    EC=[]
    for u,v in g.edges(labels=0):
        e1=('a',u,v)
        E += [(e1,(u,v))]
        e2=('a,',v,u)
        E += [(e2,(v,u))]
        EC += [e1,e2]
    G=Graph(E)
    return G

def edgeclique2tooriginal(g):
    """
    reverse edgeclique2:
    edgeclique2tooriginal(graphtoedgeclique2(g))=g
    """
    ve=[v for v in g.vertices() if g.degree(v)==1]
    E=[]
    for v in ve:
        ne=g.neighbors(v)
        assert len(ne)==1
        E += ne
    G=Graph(E,multiedges=False)
    return G

def listtoclique(l):
    E=[]
    n=len(l)
    for i in xrange(n):
        for j in xrange(i+1,n):
            E += [(l[i],l[j])]
    return E
$\endgroup$
  • $\begingroup$ Your transformation does not preserve isomorphism. Every pair of graphs with the same number of vertices and edges will have isomorphic images under your transformation. $\endgroup$ – David Hackenger Dec 20 '15 at 10:32
  • $\begingroup$ @DavidHackenger Many thanks! You gave counterexample at least. $\endgroup$ – joro Dec 20 '15 at 13:03

Your Answer

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

Browse other questions tagged or ask your own question.