Ask Math Problems

82 readers

1 users here now

founded 8 months ago

MODERATORS

[email protected]

Graph isomorphism (sopuli.xyz)

submitted 8 months ago* (last edited 8 months ago) by [email protected] to c/[email protected]

7 comments fedilink hide all child comments

Definitions

A graph G = (V, E) is a set of nodes V and a set of undirected edges E. An undirected edge is a set of two vertices.

Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorph if there is a bijective mapping f from V1 to V2 such that f(E1) = E2. Applying f to E1 means applying it to each node in each edge in E1.

Problem

Is there an algorithm that decides if two arbitrary graphs are isomorphic in polynomial time?

top 7 comments

sorted by: hot top controversial new old

[–] [email protected] 3 points 8 months ago (1 children)

Unless I'm reading your question wrong, it's an open question so nobody knows

[–] [email protected] -1 points 8 months ago

That's why I'm asking

[–] [email protected] 3 points 8 months ago

I would think a good way is to find an ordering of nodes. If you can order the nodes of any graph in a repeatable way depending only on the graphs shape, then the ordered form of V1 and V2 should be identical, and ordering E1 and E2 by their nodes would also yield identical lists, if and only if the graphs are isomorphic.

An easy start would be ordering by number of connections, but this of course is in no way sufficient.

[–] Feathercrown 3 points 8 months ago* (last edited 8 months ago) (2 children)

Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorph if there is a bijective mapping f from V1 to V2 such that if f(E1) = E2.

If f(E1) = E2 then what?

[–] Feathercrown 3 points 8 months ago* (last edited 8 months ago) (1 children)

Is there an algorithm that decides if two arbitrary graphs in polynomial time?

If two arbitrary graphs are what? I assume isomorphic.

[–] [email protected] 2 points 8 months ago

Fixed

[–] [email protected] 3 points 8 months ago

Fixed