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?

$\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$ 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$ Jan 11, 2016 at 18:27
  • $\begingroup$ @TylerSeacrest Many thanks! I missed that and likely it is explanation. $\endgroup$
    – joro
    Jan 12, 2016 at 8:02

0

Your Answer

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

Browse other questions tagged or ask your own question.