1
$\begingroup$

Given a directed graph $G=(V,E)$, we know that there are efficient algorithms (i.e., linear in the number of nodes and edges) for detecting cycles in it. But this uses the fact that a basic task such as determining whether there is a vertex from $v_1$ to $v_2$ is easy.

Suppose, however, that the size of $G$ (i.e., the number of nodes) is exponential, and that, given $v_1,v_2\in G$, the complexity of determining whether there is an edge from $v_1$ to $v_2$ is $\mathsf{PSPACE}$-complete.

My question is: given only this amount of information, is it somehow obvious/straightforward what the complexity of finding a cycle in $G$ is (e.g., whether it is $\mathsf{EXPTIME}$-hard, or something like that)?

As a sidenote, I haven't said where these graphs come from. They're some combinatorial objects generated from some other stuff, and I'm curious whether the complexity issue needs a bona-fide reduction using the particulars of the situation, or if there's some quick general argument that applies here, and which I'm missing.

Improve this question
$\endgroup$
5
  • $\begingroup$ It seems likely that the class of graphs is quite special, so is there a reason to think that special-purpose algorithms to decide the presence of cycles are not possible? From the other side, is it already hard to determine whether there is a trivial cycle (say, a triangle) in these graphs? $\endgroup$
    – András Salamon
    Commented May 17, 2018 at 20:28
  • $\begingroup$ How is $G$ specified? Perhaps we are given a formula $\varphi(x,y)$ that evaluates to true if the graph contains an edge from $x$ to $y$, or false otherwise? Or something else? To make this an algorithmic question, you need to specify how $G$ is represented on the input. Alternatively, if you want to know about a single particular graph $G$, as András Salamon explains, there might well be some better algorithm that exploits the structure of $G$; it's not going to be possible to answer the question without knowing the particular graph $G$ (or class of graphs) you have in mind. $\endgroup$
    – D.W. ♦
    Commented May 17, 2018 at 22:16
  • $\begingroup$ Thanks, this already answers the question to some extent. I realize the problem is somewhat vaguely specified, but that was intentional as I wanted to know if the complexity falls out naturally just from the given information. $\endgroup$
    – Palmy
    Commented May 18, 2018 at 8:01
  • $\begingroup$ My reasoning yesterday was as follows: to determine whether there is an edge from $v$ to $v$, given $v$, is already $\mathsf{PSPACE}$-complete. So suppose I now want to determine whether there is a cycle: then I have to store at least the 'visited' nodes. Since there are exponentially many nodes in $G$ (think all possible assignments to some variables), in the worst case (when $G$ itself is a big cycle), I have to store an exponential number of nodes, which shows the problem is in $\mathsf{EXPTIME}$. But I guess this, by itself, gives no hint on whether it's $\mathsf{EXPTIME}$-hard, right? $\endgroup$
    – Palmy
    Commented May 18, 2018 at 8:10
  • $\begingroup$ Ok, yes, it's obvious we can't tell just from that. For instance, if you somehow happen to know that $G$ is a linear order (or a tree or something), then you don't need to do any additional checking. And the fact that checking whether there's an edge from $v_1$ to $v_2$ is $\mathsf{PSPACE}$-complete has no bearing on this. It was a dumb question, sorry. :) $\endgroup$
    – Palmy
    Commented May 18, 2018 at 8:26

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.