7
$\begingroup$

Thesis and a paper give conflicting claims about the complexity of graph isomorphism for directed path graphs.

Since this means GI is polynomial likely I am missing something or there is something else wrong.

Intersection Graph Algorithms, Dietz, Paul F. claims:

... Using this fact I develop a polynomial time algorithm for directed path graph isomorphism.

Directed path graph isomorphism, Luitpold Babel, Ilia Ponomarenko, Gottfried Tinhofer

We prove that deciding isomorphism of directed path graphs is isomorphism complete (Theorem 1).

The definition of directed path graph appears the same to me in both.

All authors appear heavily cited.

What is wrong with this result that graph isomorphism is polynomial?

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you tried emailing the authors of the latter paper? pdmi.ras.ru/~inp or unibw.de/bw/institute/mathematik_informatik/mi_professuren/… $\endgroup$
    – Timothy Chow
    Commented Jan 11, 2016 at 16:26
  • 2
    $\begingroup$ I think in the thesis Dietz defines a directed tree as being rooted (see page 7 (page 19 of the electronic file)). If so, then both authors agree that directed path graph isomorphism problem on rooted trees is polynomial, while only the paper talks about unrooted trees (and that the problem is complete). $\endgroup$
    – Tyler Seacrest
    Commented Jan 11, 2016 at 18:27
  • $\begingroup$ @TylerSeacrest Many thanks! I missed that and likely it is explanation. $\endgroup$
    – joro
    Commented Jan 12, 2016 at 8:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .