1
$\begingroup$

I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to enumerate so many possibilities that it would be useless compared to other approaches. So, to consider some remote (but who nows..) implications of my approach to complexity theory I wonder what's the complexity of the one sink directed subgraph isomorphism problem, or, if this is not known, the complexity of the one sink directed graph isomorphism problem.

Also, I believe that the general directed subgraph isomorphism problem is np-complete just like the undirected one, since any undirected graph can be converted to an equivalent directed one (by replacing each edge by two other incident on the same node) and so if I solve for the last I solve for the first. Please correct me if I am wrong.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ The one sink restriction is no restriction at all. You can just endow any given directed graph with a new sink connected to all original vertices. $\endgroup$
    – Emil Jeřábek
    Apr 4, 2015 at 14:29
  • $\begingroup$ @EmilJerábek Thank you! I had discarded that idea because I thought it would not solve my real problem which was how to 'order' in my model the original sinks mapped to the new artificial one. But your comment made me come back to that and realize the obvious: even with natural one sink graphs I would get the very same problematic scenarios. So this was really an artificial restriction. Now I think I have found a way to deal with this... $\endgroup$
    – Fernando Pimentel
    Apr 5, 2015 at 21:44

0

Reset to default

Your Answer

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