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

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

<p>Moreover, $G&#39;$ has a cycle iff $G$ has a cycle, therefore $G&#39;$ satisfies $\text{CYCLE} \cup \text{NODIAG}$ iff $G$ satifies $\text{CYCLE}$. Therefore $\text{CYCLE}\cup \text{NODIAG}$ is NL-hard. </p>

<p>I think a similar construction would work for every purely universal property. </p>

CC BY-SA 3.0
2011-09-29T12:54:53.437Z
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.
Michaël Cadilhac
CC BY-SA 3.0
2011-09-29T13:54:03.300Z
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}$.
Jan Johannsen
CC BY-SA 3.0
2011-09-29T15:24:12.687Z
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.
Michaël Cadilhac
CC BY-SA 3.0
2011-09-29T16:15:09.233Z
(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)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.5612) by Tesson and Therien.)
Michaël Cadilhac
CC BY-SA 3.0
2011-09-30T07:52:18.073Z
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.
Jan Johannsen
CC BY-SA 3.0
2011-09-30T13:03:09.110Z
I'm not sure this would work.  If $G = \langle \{u, v, x, y\}, \{(u, v), (x, y)\}\rangle$, then this operation will leave the excluded structure, right?  And if $G$ is a single node $u$ with $(u, u)$, which does not have the excluded graph, then $G'$ has $u, v_e$ and edges $(u, v_e)$ and $(v_e, u)$, which has the excluded structure.  Did I get it right?
Michaël Cadilhac
CC BY-SA 3.0
2011-09-30T14:14:50.483Z
I'm not sure I understand what you mean by excluded structure here then. I assumed that you meant $\cap$ instead of $\cup$ in the above description, i.e., for any two edges $(u,v)$ and $(u',v')$ the "diagonal" edges $(u,v')$ and $(u',v)$ should not be there. $G'$ in my more recent construction has this property.
Jan Johannsen
CC BY-SA 3.0
2011-09-30T21:02:34.907Z
Sorry Jan, my current wording is exact, and I do mean $\cup$.  I think Adrien addressed the "actual problem," which seems to show that the problem is not NL-complete.  Still, the problem (the general one) with $\cap$ seems nontrivial either, thanks for pointing out this variant!  Again, thank you for your work.
Michaël Cadilhac
CC BY-SA 3.0
2011-09-29T08:01:40.623Z
2011-09-29T08:47:03.827Z
2011-09-29T08:47:03.827Z
Jan Johannsen
<p>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.</p>

<p>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)$.</p>

<p>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.</p>

<p>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))]$</p>

CC BY-SA 3.0
2011-09-30T21:05:04.427Z
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.
Michaël Cadilhac
CC BY-SA 3.0
2011-10-02T15:30:01.570Z
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\}$.
Jan Johannsen
CC BY-SA 3.0
2011-10-02T20:48:09.930Z
@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.
Michaël Cadilhac
CC BY-SA 3.0
2011-09-30T18:39:16.787Z
2011-09-30T18:39:16.787Z
Adrien
<p><strong>Context:</strong>  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.</p>

<p><strong>Actual problem:</strong> 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.</p>

<p><strong>Question:</strong> 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?</p>

<p>Thanks for your input!</p>

<cc.complexity-theory><graph-theory><descriptive-complexity>
When does an FO property kill off NL-hardness?
Michaël Cadilhac
# When does an FO property kill off NL-hardness?

(Asked by: username_0 on 2011-09-28)

**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!

**Tags:** cc.complexity-theory, graph-theory, descriptive-complexity

---

## 2 answers

### Answer by username_1 on 2011-09-29. Score: 4

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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}$.  
> **username_0**: 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.  
> **username_0**: (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)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.5612) by Tesson and Therien.)  
> **username_1**: 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.  
> **username_0**: I'm not sure this would work.  If $G = \langle \{u, v, x, y\}, \{(u, v), (x, y)\}\rangle$, then this operation will leave the excluded structure, right?  And if $G$ is a single node $u$ with $(u, u)$, which does not have the excluded graph, then $G'$ has $u, v_e$ and edges $(u, v_e)$ and $(v_e, u)$, which has the excluded structure.  Did I get it right?  
> **username_1**: I'm not sure I understand what you mean by excluded structure here then. I assumed that you meant $\cap$ instead of $\cup$ in the above description, i.e., for any two edges $(u,v)$ and $(u',v')$ the "diagonal" edges $(u,v')$ and $(u',v)$ should not be there. $G'$ in my more recent construction has this property.  
> **username_0**: Sorry Jan, my current wording is exact, and I do mean $\cup$.  I think Adrien addressed the "actual problem," which seems to show that the problem is not NL-complete.  Still, the problem (the general one) with $\cap$ seems nontrivial either, thanks for pointing out this variant!  Again, thank you for your work.  

---

### Answer by username_2 on 2011-09-30. Score: 2

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))]$

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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\}$.  
> **username_0**: @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.  

---

