Characterizing cycles in a directed graph with optional edges

Question

Consider a directed graph in which some edges are marked as "optional". A graph with $N$ optional edges induces a family of $2^N$ graphs depending on which edges are removed. In some cases, some of these graphs may be acyclic while others contain cycles.

For example, consider the graph with vertices $\{1, 2, 3, 4\}$ and edges $\{1 \rightarrow 2,\ 2 \xrightarrow{?} 3,\ 3 \rightarrow 1,\ 2 \xrightarrow{?} 4,\ 4 \xrightarrow{?} 1\}$ where the optional edges are the ones marked with a question mark.

This defines a family of eight different graphs with the same vertices but different sets of edges. If we denote the presence or absence of an edge between vertices $u$ and $v$ as $E(u \rightarrow v)$, then the following Boolean expression describes whether a particular graph in this family in cyclic: $E(2 \rightarrow 3) \vee [E(2 \rightarrow 4) \wedge E(4 \rightarrow 1)]$

Given a particular graph containing some optional edges, I'd like to be able to describe compactly the combinations of optional edges that must be present for the graph to be cyclic without having to specify the entire original graph. In particular, I'd like to know if there is a description whose length is polynomial in the number of optional edges rather than the total number of edges.

More formally: Is there a pair of (ideally efficient) algorithms $P$ and $Q$ such that $P$ takes in a description of a directed graph with $N$ optional edges and produces an "encoded" string whose length is polynomial in $N$, and Q can read in that encoded string and a subset of the $N$ optional edges and determine whether, with those edges present (and the other optional edges removed), the original graph would be cyclic?

Answer 1

Yes, this is doable. An encoded string of length $O(N^2)$ suffices.

Let me describe how to do it. Let $V'$ denote the set of vertices that are the endpoints of the optional edges. Obviously, $|V'| \le N$. I'll describe the two procedures P,Q below.

Procedure P: Compute reachability information for each pair of vertices in $V'$. In other words, for each $s,t \in V'$, compute whether $t$ is reachable from $s$ in the original graph (without using any optional edge); the answer is either "yes" or "no". Note that there are $O(N^2)$ pairs $s,t$, so we can encode the answer to all those questions using $O(N^2)$ bits (one bit per pair $s,t \in V'$). Let this be the encoded string. Of course, the length of this encoded string is polynomial in $N$.

In particular, we can think of this encoded string as the representation of a graph $G'=(V',E')$. $G'$ has vertices $V'$ and has an edge $s\to t$ if and only if $t$ is reachable from $s$ in the original graph (without optional edges). The length of the encoding of $G'$ is $O(N^2)$, so polynomial in $N$.

Procedure Q: Given a set $S$ of optional edges and the encoded string, here's how we can tell whether adding those edges would create a cycle. Basically, add every edge in $S$ to the graph $G'$. (The encoded string tells us $G'$, so we can treat $G'$ as known, i.e., it is one of the inputs to Q.) Now you can do depth-first search in the resulting graph, $G''=(V',E' \cup S)$, to test whether $G''$ contains any cycle. $G''$ will have a cycle if and only if adding $S$ to the original graph (without any other optional edges) has a cycle.