10
$\begingroup$

Context: We consider only digraphs. Let CYCLE be the language of graphs with a cycle; it is an NL-complete problem. Let HASEDGE be the language of graphs with at least one edge. Then trivially, $\text{CYCLE} \cup \text{HASEDGE}$ is no longer NL-hard, while $\text{CYCLE} \cup \overline{\text{HASEDGE}}$ stays so.

Actual problem: I'm wondering if the language $$\text{CYCLE} \cup \{(V, E):(\exists u,v,x,y)[E(u, v) \land E(x, y) \land \neg E(u, y) \land \neg E(x, v)]\}$$ is still NL-hard.

Question: For which FO formula $\phi$ on the vocabulary of graphs is $$\text{CYCLE} \cup \{(V, E) : (V, E) \models \phi\}$$ NL-hard? Is this property decidable?

Thanks for your input!

| cite | improve this question | |
$\endgroup$
4
$\begingroup$

Let me call the property in your "Actual Problem" $\text{NODIAG}$. The following mapping reduces $\text{CYCLE}$ to $\text{CYCLE} \cup \text{NODIAG}$:

For a given $G=(V,E)$, replace every vertex $v$ in $G$ by two copies $v$ and $v'$, and if there is an edge $(u,v)$ in $E$, let $G'$ have edges $(u,v), (u,v'), (u',v)$ and $(u',v')$. Thus for every $G$ the graph $G'$ satisfies $\neg \text{NODIAG}$.

Moreover, $G'$ has a cycle iff $G$ has a cycle, therefore $G'$ satisfies $\text{CYCLE} \cup \text{NODIAG}$ iff $G$ satifies $\text{CYCLE}$. Therefore $\text{CYCLE}\cup \text{NODIAG}$ is NL-hard.

I think a similar construction would work for every purely universal property.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your work Jan! But I'm not sure you addressed the problem completely, for if a NODIAG structure appears in G, it still appears at the end of your construction, AFAIU. $\endgroup$ – Michaël Cadilhac Sep 29 '11 at 12:54
  • $\begingroup$ Yes, but so what. The construction enforces that $G'\models \neg \text{NODIAG}$. So if $G\models \text{CYCLE}$, then $G'\models \text{CYCLE}$, hence $G'\models \text{CYCLE} \cup \text{NODIAG}$. OTOH, if $G\not\models \text{CYCLE}$, then $G'\not\models \text{CYCLE}$, and hence $G'\not\models \text{CYCLE} \cup \text{NODIAG}$. Thus the construction reduces $\text{CYCLE}$ to $\text{CYCLE} \cup \text{NODIAG}$. $\endgroup$ – Jan Johannsen Sep 29 '11 at 13:54
  • $\begingroup$ Jan, I'm deeply sorry, I messed up with the wording of my question; the subgraph described was to be thought as an EXCLUDED graph. Note that with the previous wording, you'd just need to add four fresh nodes $u,v,x,y$ and edges $u \to v$, $x \to y$, and $u \to y$ for the graph to be out of NODIAG. Again, I'm very sorry for the typos. $\endgroup$ – Michaël Cadilhac Sep 29 '11 at 15:24
  • $\begingroup$ (PS: As I owe you for working on a misworded question, here is a TCS paper with a nice title that does not appear in your list: Diamonds are Forever (The Variety DA) by Tesson and Therien.) $\endgroup$ – Michaël Cadilhac Sep 29 '11 at 16:15
  • $\begingroup$ In that case, how about just adding a new vertex in every edge: in $G$ replace every $e = (u,v)$ by $(u,v_e)$ and $(v_e,v)$. The resulting graph $G'$ is cyclic iff $G$ is, and does not have the excluded structure. BTW I'm not maintaining that list any longer. $\endgroup$ – Jan Johannsen Sep 30 '11 at 7:52
2
$\begingroup$

The actual problem is in FO. Testing if there exists $a,b,c,d \in V(G)$ such that $(a,c),(b,d) \in E(G)$ and $(a,d),(b,c) \notin E(G)$ is obviously in FO.

Assume that there are no such $a,b,c,d$, then $G$ admits a directed cycle if and only if $G$ admits a directed cycle of length two. This can be deduced from the fact that for any two vertices $a$ and $b$ of $G$, their out-neighbourhoods $N^-(a)$ and $N^-(b)$ are such that $N^-(a) \subseteq N^-(b)$ or $N^-(b) \subseteq N^-(a)$.

Thus, it's sufficient to check if there exists $a,b \in V(G)$ such that $(a,b),(b,a) \in E(G)$, which is in FO.

So, $G$ is in $CYCLE \cup NODIAG$ if and only if $(\exists a,b,c,d)[(E(a,b) \wedge E(c,d) \wedge \neg E(a,d) \wedge \neg E(b,c)) \vee (E(a,b) \wedge E(b,a))]$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Adrien. Would you care adding an argument as of why the out-neighborhoods of any two nodes are comparable? I'll wait a little bit to see if anyone addresses the complete problem, and if no one shows up, I'll go for your answer. $\endgroup$ – Michaël Cadilhac Sep 30 '11 at 21:05
  • $\begingroup$ I don't think that the comparability of out-neighborhoods really holds. Take e.g. the graph of just four vertices $a,b,c,d$ with edges $(a,c)$ and $(b,d)$. This graph satisfies Michael's formula, but $N^-(a) = \{ c\}$ is incomparable with $N^-(b) = \{ d\}$. $\endgroup$ – Jan Johannsen Oct 2 '11 at 15:30
  • $\begingroup$ @Jan: If I'm not mistaken, Adrien's point is that if a graph <i>does not</i> satisfy the second part, then if it has a cycle, it has a cycle of length 2. So his point is that if the graph <i>does not</i> satisfy the second part, then the comparability holds. $\endgroup$ – Michaël Cadilhac Oct 2 '11 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.