# When does an FO property kill off NL-hardness?

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?

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.

• 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. Commented Sep 29, 2011 at 12:54
• 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}$. Commented Sep 29, 2011 at 13:54
• 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. Commented Sep 29, 2011 at 15:24
• (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.) Commented Sep 29, 2011 at 16:15
• 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. Commented Sep 30, 2011 at 7:52

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

• 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. Commented Sep 30, 2011 at 21:05
• 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\}$. Commented Oct 2, 2011 at 15:30
• @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. Commented Oct 2, 2011 at 20:48