Safe Sequences via Dominators in DAGs for Path-Covering Problems

In this paper we consider directed graphs, especially directed acyclic graphs (DAGs). For a DAG $G=(N,A)$ with node set $N$ and arc set $A$, we let $n=|N|$ and $m=|A|$. We denote an arc from $u$ to $v$ as $uv$ and a path $p$ through nodes $v_1,\mathrm{\dots },v_k$ as $p=v_1\mathrm{\dots }{v}_k$. Two paths are considered distinct if they differ in at least one node. The set of in-neighbors (out-neighbors) of a node $v$ is denoted $N_v^{-}$ ($N_v^{+}$), and its indegree (outdegree) as $d_v^{-}$ ($d_v^{+}$). For nodes $u,v$ we say that there is a $u$-$v$ path if there is a path whose first node is $u$ and last node is $v$ (we also say that $u$ reaches $v$). An antichain is a set of pairwise unreachable nodes. The size of the largest antichain in a DAG is called width. Analogously, for arcs $uv,xy$ we say that $uv$ reaches $xy$ if $v$ reaches $x$. An arc-antichain is a set of pairwise unreachable arcs, and the arc-width of a DAG is the size of the largest arc-antichain of the graph.

For $X\subseteq N$ we denote a sequence $X$ through nodes $u_1,\mathrm{\dots },u_{\mathrm{\ell }}$ as $X=u_1,\mathrm{\dots },u_{\mathrm{\ell }}$ if there is a $u_i$-$u_{i+1}$ path for all $1\le i\le \mathrm{\ell }-1$; in particular, a path is a sequence. We say that $X$ covers or contains a node $v$ if $v=u_i$ for some $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$, and we write $u\in X$. If $Y$ is a sequence and each node of $X$ is contained in $Y$ we say that $X$ is a subsequence of $Y$, or that $X$ is contained in $Y$. Since $G$ is a DAG, the nodes of $X$ appear in the same order as in $Y$.

Let $X^{\prime }=v_1,v_2,\mathrm{\dots },v_{{\mathrm{\ell }}^{\prime }}$ be a sequence such that there is a path from the last node $u_{\mathrm{\ell }}$ of $X$ to $v_1$. The concatenation of $X$ and $X^{\prime }$ is simply the sequence $X{X}^{\prime }$ obtained as $X$ followed by $X^{\prime }$. If $u_{\mathrm{\ell }}=v_1$, then the repeated occurrence of $v_1$ is removed, i.e. $X{X}^{\prime }:=u_1,\mathrm{\dots },u_{\mathrm{\ell }},v_2,\mathrm{\dots },v_{{\mathrm{\ell }}^{\prime }}$. We adopt the convention that lowercase letters $u,v,w,x,y,z$ denote nodes and uppercase letters $X,Y$ denote sequences of nodes.

We define a path cover of $G$ to be a set $P$ of $s$-$t$ paths such that $\forall u\in N\exists p\in P:u\in p$; we also say cover instead of “$s$-$t$ path cover of $G$” when the graph $G$ is clear from the context. Two path covers are distinct if they differ in at least one path. We assume that every node of $G$ lies in some $s$-$t$ path. We say that a sequence $X$ is safe for $G$ if in every path cover $P$ of $G$ it holds that $X$ is a subsequence of some path in $P$. If $X$ is not safe we say that it is unsafe. A sequence $X$ is maximally safe if it is not a subsequence of any other safe sequence. We assume that there is always an $s$-$t$ path containing a given sequence of nodes, otherwise that sequence is vacuously unsafe. Note that imposing the collection of $s$-$t$ paths of a cover to be minimal with respect to inclusion results in an equivalent definition of safety: any sequence that is safe for path covers is also safe for minimal path covers since every minimal path cover is a path cover; but also, if $X$ is safe for minimal path covers then it is also safe for general path covers, as otherwise we could have a path cover $P$ avoiding $X$ from which arbitrary $s$-$t$ paths can be removed until $P$ becomes minimal.

We define a unitary path as a path where each node has indegree equal to one but the first one, and each node has outdegree equal to one but the last one. For example, in Figure 1, the paths $de$ and $pq$ are unitary, the path $cde$ is maximally unitary. With respect to $G$, we define the compressed graph of $G$ as the graph where every maximal unitary path of $G$ is contracted into a single node. It is a folklore result that compressing a graph can be done in linear time (see e.g. [13, 52]). We state this fact in the next lemma together with an additional property stating that compressed graphs cannot have arcs $uv$ with $v$ the unique out-neighbor of $u$ and $u$ the unique in-neighbor of $v$, since $uv$ would then be a unitary path.

The compression of unitary paths preserves safety: every $s$-$t$ path in $G$ traversing the unitary path traverses the corresponding node in the compressed graph of $G$, and every $s$-$t$ path traversing a node in the compressed graph of $G$ necessarily traverses the unitary path it corresponds to in $G$. This idea appeared in the context of walk-finding problems in [11].

In the dominator literature, the directed graphs on which dominators are computed have a single start node $s$ from which every node is reachable. In some cases, the graphs have instead or additionally a unique sink $t$ which is reached by every node, in which case the dominance relation is referred to as post-dominance (see e.g., [5, 27]). A prominent application of dominators is in the context of program analysis, where $s$ corresponds to the entry point of the program and $t$ to its exit point. Our graphs always have unique abstract nodes $s$ and $t$, hence, diverging from standard notation, we parameterize the domination relation by $s$ and $t$. We borrow standard concepts and notation from the literature of dominators, which we describe next.

Let $G$ be an $s$-$t$ directed graph. A node $u$ is said to $s$-dominate a node $v$ if every $s$-$v$ path contains $u$, hence $u$ is an $s$-$v$ cutnode if and only if $u$ $s$-dominates $v$. Every node $s$- and $t$-dominates itself. We also say that $v$ $t$-dominates $u$ if every $u$-$t$ path contains $v$, which is equivalent to $v$ being a $u$-$t$ cutnode. We say that $u$ strictly $s$-dominates $v$ if $u$ $s$-dominates $v$ and $u\ne v$. For $v\ne s$, the immediate $s$-dominator of $v$ is the strict $s$-dominator of $v$ that is dominated by all the nodes that strictly dominate $v$, in which case we write $ido{m}_s(v)=u$. The domination relation on $G$ with respect to $s$ can be represented as a rooted tree at $s$ with the same nodes as $G$, called the $s$-dominator tree of $G$. In this tree, the parent of every node is its immediate $s$-dominator, every node is $s$-dominated by all its ancestors and $s$-dominates all its descendants and itself. A node is said to be an $s$-dominator if it strictly $s$-dominates some node. The same terminology will be used for the $t$-domination relation. We also define a function $dom:N\times {\mathbb{N}}^{+}\to N$ on rooted trees as follows. Let $do{m}_s(v,k):=ido{m}_s(v)$ when $k=1$ and $do{m}_s(v,k):=do{m}_s(do{m}_s(v,1),k-1)$ when $k>1$. If $k$ is larger than the number of strict dominators of a given node, then it defaults to $s$ (resp. $t$) in the $s$-dominator tree (resp. $t$-dominator tree). Essentially, $dom$ gives the $k$-th ancestor of a node in a rooted tree, if it is well defined, otherwise it returns the root of the tree. For example, in Figure 1, the immediate $s$-dominator of $b$ is $a$ ($do{m}_s(b,1)=a$) and $do{m}_t(q,3)=t$. Node $c$ is a strict $t$-dominator of the nodes $\{a,b,k,k^{\prime }\}$. See [23] for an in-depth presentation of dominators.

In DAGs, dominators admit a characterization, which we state in Lemma 5 below. This was first presented by Ochranová [41], but with an incomplete proof. This characterization was also discussed by Alstrupt et al. [6, Sec. 5.1]. To the best of our knowledge, we did not find a complete proof of this characterization in the literature, and hence one can be found in the extended version.

As described in Section 1.2, we study experimentally the potential of applying safe sequences in two arc-path covering problems, LeastSquares and MinPathError.

We did not use an external algorithm to compute arc-dominator trees because these are mostly tailored for node-dominators. Instead, we compute the immediate $s$-dominator and $t$-dominator of all arcs with an $O(m^2)$ time procedure via the algorithm of [9], appropriately handling the reversed graph of $G$ for the immediate $s$-domination relation. The classical algorithm of Aho and Ulman [3] to build dominator trees has the same running time as our procedure. We remark that even with a suboptimal algorithm to compute the dominator trees, our entire safety-preprocessing step takes less than 0.1 seconds on average.

With the dominator trees, we can compute all the maximal safe sequences with respect to arbitrary subsets $C\subseteq A$ of arcs to be covered, all in time proportional to the total length of all the maximal safe sequences, completely analogously to the discussion in Section 3.

The ILPs were optimized as in [25] by fixing $x_{uvi}$ variables to 1 based on the maximal safe sequences of the input DAG, which reduces the search space of the linear program and hence speeds-up the solver. Let $X_1,\mathrm{\dots },X_t$ be sequences in the input DAG such that: (a) each $X_i$, $i\in \{1,\mathrm{\dots },t\}$, must appear in some solution path of the ILP, and (b) there exists no path in the DAG containing two distinct $X_i$ and $X_j$. In the case that every $X_i$ is a path, Grigorjew et al. [25] noticed that if the two mentioned properties hold, then $X_1,\mathrm{\dots },X_t$ must appear in $t$ distinct paths of among the $k$ solution paths of the ILP (see the three solid-colored sequences shown in Figure 1 which must appear in different paths of any path cover). As such, without loss of generality, one can set $x_{uvi}=1$ for each arc $uv$ of $X_i$, for all $i\in \{1,\mathrm{\dots },t\}$. When using sequences to set binary variables, we can proceed in a completely analogous manner. To have a large number of binary variables set to 1, we follow the approach of [25]. Namely, for every arc $uv$, we define its weight as the length of the longest safe sequence containing $uv$. Then we find a maximum-weight antichain of arcs in the DAG using the min-flow reduction of [39]. Then, for each $a_i$ in the maximum-weight antichain, we consider a longest safe sequence $X_i$ containing $a_i$ to fix variables to 1. Note that a path covering two such sequences $X_i$ and $X_j$ would witness that $a_i$ and $a_j$ cannot be in an antichain. Finally, we set $k$ to the arc-width of the graph and run Gurobi to solve the ILP.

Note that any solution to MinPathError is also a path cover, since each arc weight is positive, and thus the simplified ILP has equivalent optimal solutions. This may not be the case for LeastSquares, since some arcs may not be covered by any solution path. To handle such scenarios we propose using maximal safe sequences for path covers where only a subset $C$ of nodes or arcs can be trusted to appear in any optimal solution. As an illustration of this approach, we perform experiments by choosing the subset $C$ as those arcs whose weight is at least as large as the 25-th percentile of the weights of all arcs, since we can heuristically infer that the solution paths of LeastSquares cover the arcs of large enough weight.

We experiment with seven datasets. The first four contain splice graphs with erroneous weights created directly from gene annotation by [16].⁶⁶6Available at https://doi.org/10.5281/zenodo.10775004 These were created starting from the well-known dataset of Shao and Kingsford [49], which was also used in several other studies benchmarking the speed of minimum flow decomposition solvers [17, 32, 54]. The original splice graphs were created in [49] from gene annotation from Human, Mouse and Zebrafish. This dataset also contains a set of graphs (SRR020730) from human gene annotation, but with flow values coming from a real sequencing sample from the Sequence Read Archive (SRR020730), quantified using the tool Salmon [42]. To mimic splice graphs constructed from real read abundances, [16] added noise to the flow value of each arc, according to a Poisson distribution. The last three datasets contain graphs constructed by a state-of-the-art tool for RNA transcript assembly, IsoQuant [44]. Mouse annotated transcript expression was simulated according to a Gamma distribution that resembles real expression profile [44]. From these expressed transcripts, PacBio reads were simulated using IsoSeqSim [1] and fed to IsoQuant for graph creation (we call this Mouse PacBio), and ONT reads were simulated using Trans-Nanosim [28], which was modified to perform a more realistic read truncation (see [44]), and fed to IsoQuant for graph creation (we call this Mouse ONT). For the latter one, there is also a simpler version where no read truncation was introduced (Mouse ONT.tr). These are available at [43].

We group the graphs in each dataset by width (column “$w$”). For each width-interval we show different metrics, namely the number of graphs “$\mathrm{\#}$g”, the average number of arcs “avg $m$” (and the maximum number of arcs in parenthesis), the time taken in seconds by the safety preprocessing step in “prep”, the percentage of fixed arc-variables $x_{uvi}$ of the ILP out of all $mk$ variables in “vars”, the number of solved instances by the ILP with and without safety in “$\mathrm{\#}$solved” (and in parenthesis the average time taken in seconds to solve those instances), and in the column “$\times$” we show the average speedup obtained by advising the linear program with safety. The speed-ups are computed by considering for each graph the ratio between the time taken by the original ILP (or 300 sec. if this timed-out) divided by the time taken by the optimized ILP, and averaging these ratios. In the “prep” and “vars” column, a dash is written only if no instance was solved with safety information. In the remaining columns a dash means not applicable.

In Table 1 we show the experimental results of the safety-optimized ILPs for MinPathError.(As explained before, for this problem it is correct to select $C=A$.) When the width of the graph is small, the speed-ups are also small. However, such graphs are fast to solve without safety in the first place. The challenging cases are the graphs of larger widths and more arcs (indeed, the solver with no safety information performs poorly and it becomes slower as the width increases). The speed-up of the solver significantly increases as the width of the graph increases, becoming more than 200$\times$ in some datasets. Moreover, these speed-up are obtained almost for free, in the sense that the time needed to compute safe sequences is negligible for all datasets, i.e. below 0.1 seconds, and often even much faster. We highlight the notable difference between the number of instances solved with no safety and with safety. In Table 2 for LeastSquares we observe the same phenomena, obtaining in some datasets speed-ups of 300$\times$ on graphs of larger widths, and solving always more instances with safety than without safety. In the extended version results for $C⊊A$ in the MinPathError and for $C=A$ in the LeastSquares can be found.