3
$\begingroup$

Confusion is possible, but two papers and a simple graph transformation imply Graph Isomorphism is polynomial, which is an open problem.

The closed neighborhood of a vertex in a graph is sometimes called the “star” of the vertex. The “star system” of a graph is then the multi-set of closed neighborhoods of all the vertices of the graph and the Star System problem is the problem of deciding whether a given system of sets is a star system of some graph

According to paper1 p.20 reconstructing the graph from its star system is GI-complete.

According to a paper2 p.3 On the Complexity of Reconstructing H-free Graphs from their Star Systems, $C_4$-free or $C_3$-free graphs can be reconstructed from their star systems.

There is isomorphism preserving graph transformation (given in paper1) $G \to G'$ where $G'$ is chordal and hence $C_4$ free. The transformation is $V(G')=V(G) \cup E(G)$. In $G'$ add a clique of $V(G)$ and for $u,v \in E(G)$ add the edges $((u,v),u),((u,v),v)$. $G'$ is $C_4$-free, chordal and split.

For $C_3$-free graph just take the subdivision of $G$, which is bipartite and triangle free.

Does this prove GI is polynomial?

$\endgroup$
1
  • 5
    $\begingroup$ The problem is not about reconstructing a graph from its stars, but of determining whether any graph has a given multiset of stars. Note that lots of graphs have the same multiset of stars without being isomorphic. $\endgroup$ Jun 28, 2019 at 14:52

0

Your Answer

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