Characterizing cycles in a directed graph with optional edges
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.