Representing Paths in Digraphs

Graph string matching and approximate matching have been widely investigated due to their application in the context of pattern matching of hypertexts [1, 2, 20, 17] and panegenome analysis [19, 25, 5]. The problems consider a query string $s$ and a directed graph $D$, whose nodes are labeled with symbols or strings. A path or a walk in $D$ is associated with a string that is obtained by concatenating the symbols or the strings on the path (or walk) nodes. The problems ask whether there exists a path or a walk that matches, or approximately matches, the query string. In exact matching the two strings have to be identical, while in approximated matching edit operations may be applied on the query string or on the node labels, in order to obtain two identical strings, and such edit operations have to be minimized.

Both matching and approximate matching can be solved in polynomial time if the input graph is a Directed Acyclic Graph (DAG) [17]. When the input digraph admits cycles the exact matching is solvable in polynomial time  [1, 2, 20, 18, 13] and conditional lower bounds [8] show that improving the algorithms known in the literature is unlikely. The approximate matching is solvable in polynomial time when edit operations are applied only in the query string [13] and it is instead NP-hard when the edit operations may be applied on node labels [2], also for binary alphabet [13, 6].

A second research direction that has been recently investigated in sequence analysis, in the context of computational genomics, is the quest for subsequences of a given string that contain all symbols of the alphabet (and that have other specific properties)  [21, 7, 15, 3, 16]. The property that each symbol of the alphabet is contained in a subsequence of a given string $s$ is applied in [21] looking for a run subsequence of maximum length, where a run subsequence contains at least one substring for each symbol of the alphabet. Another approach is considered in [15, 16] and it looks whether there exists a subsequence of $s$ that consists of substrings of repeated symbols that have length at least two, with the constraint that the subsequence contains each symbol of the alphabet. Both problems are NP-hard [21, 16] and results on their tractability have been given [21, 7, 3, 15, 16].

In this contribution, we introduce new problems that aim to integrate the two aforementioned approaches. On the one hand we consider a DAG having nodes labeled by symbols over an alphabet $\mathrm{\Sigma }$, since this allows us to represent variants of a sequence as in graph string matching. On the other hand we look for a path that contains all (or the maximum number of) symbols of $\mathrm{\Sigma }$, in a similar way to the second approach. If there exists a path in the DAG that contains all the symbols of the alphabet, we call this a representing path. We introduce a decision problem, called $\mathrm{\Sigma }$-Representing Path, where we ask whether there exists a representing path in a DAG $D$. Since in some cases a representing path may not exist, we consider an optimization variant, called Maximum Representing Path, where we look for a path in $D$ that represents the maximum number of symbols in $\mathrm{\Sigma }$, that is the string associated with the path contains the maximum number of symbols of $\mathrm{\Sigma }$. Next, we summarize our results.

We start in Section 2 by presenting some concepts and by formally defining the two problems, $\mathrm{\Sigma }$-Representing Path and Maximum Representing Path. Then we investigate the complexity of the problems and we prove in Section 3 that $\mathrm{\Sigma }$-Representing Path is NP-complete even when each symbol labels at most three nodes of the input DAG, and Maximum Representing Path is APX-hard when each symbol labels at most two nodes of the DAG. Moreover, in both aforementioned cases, the input DAG has also the maximum degree bounded by three. In Section 3 we prove also a lower bound on the approximation: Maximum Representing Path cannot be approximated with factor $\frac{e}{e-1}-\alpha$, for any constant $\alpha >0$, unless $NP\subseteq DTIME({|V|}^{O(\log \log |V|)})$, where $V$ is the set of nodes of the input DAG. We complement the first hardness result by showing in Section 4 that $\mathrm{\Sigma }$-Representing Path can be solved in polynomial time when each symbol labels at most two nodes of $D$.

Then we study in Section 5 how the complexity of the two problems is influenced by the structure of $D$. Observe that if $D$ consists of a set of disjoint paths (except for the source and the target nodes of $D$), then the two problems are easy to solve by inspecting each path independently. We show that $\mathrm{\Sigma }$-Representing Path and Maximum Representing Path are W[1]-hard for parameter distance to disjoint paths. Finally, in Section 6 we present an approximation algorithm for the Maximum Representing Path problem of factor $\sqrt{OPT}$, where $OPT$ is the value of an optimal solution of Maximum Representing Path. We conclude the paper in Section 7 pointing out some future directions. Some of the proofs are not included due to page limit (marked with ${(}^{\ast })$).

We introduce some notation. For a natural number $n\in \mathbb{N}$, we denote $[n]=\{1,\mathrm{\dots },n\}$. A Directed Acyclic Graph (DAG) $D=(V,A)$ is a directed graph consisting of a set $V$ of nodes, a set $A=\{(u,v):u,v\in V\}$ of arcs, such that there is no directed cycle in $D$. Given a finite alphabet $\mathrm{\Sigma }$ and a DAG $D=(V,A)$, we define a labeling function $\lambda$ that associates a symbol with each node of $D$, that is, $\lambda :V\to \mathrm{\Sigma }$.

A path $p$ in $D$ is a sequence $v_{p,1}\mathrm{\dots }{v}_{p,z}$ ($v_{p,i}$ represents the $i$-th node of path $p$) of adjacent distinct nodes of $V$, that is $(v_{p,i},v_{p,i+1})\in A$ for $i\in [z-1]$ and $v_{p,i}\ne v_{p,j}$, for each $i,j\in [z]$ with $i\ne j$. The path is called a $v_{p,1}-v_{p,z}$ path, since it starts from $v_{p,1}$ and ends in $v_{p,z}$. The set $\mathrm{\Sigma }(p)$ of symbols represented by $p$ is defined as follows:

A path $p$ in $D$ (labeled by $\lambda$) is $\mathrm{\Sigma }$-representing if $\mathrm{\Sigma }(p)=\mathrm{\Sigma }$ (an example is given in Fig. 1); we denote the nodes of the path as $V(p)$. When a path $p$ contains a node labeled by symbol $c\in \mathrm{\Sigma }$, we say that $p$ covers $c$. We denote the length of $p$ (the number of nodes in $p$) by $|p|$. A longest path in a graph is a path having maximum length. Finding a longest path in a graph is an NP-hard problem and even hard to approximate [14], but in DAGs it can be computed in linear time [22]. Now, we define the first problem we study in this paper (we assume that the labeling $\lambda$ is surjective, so each symbol in $\mathrm{\Sigma }$ is associated with at least one node of the input graph $D$).

Since there are cases where a DAG does not contain an $s-t$-path in $D$ that is $\mathrm{\Sigma }$-representing (see the example in Fig. 1), we consider a second problem, where we look for an $s-t$-path in $D$ that contains the maximum number of distinct symbols of $\mathrm{\Sigma }$.

Given a DAG $D=(V,A)$ and a node $v\in V$, the degree of $v$ is the number of arcs incoming to $v$ or outgoing from $v$, that is

The transitive closure of $D$ is a graph $D^{\prime }=(V,A^{\prime })$ where $A^{\prime }$ is defined as follows:

Given two DAGs $D_1=(V_1,A_1)$ and $D_2=(V_2,A_2)$, with $V_1\cap V_2=\mathrm{\varnothing }$, having source nodes $s_1$, $s_2$, respectively, and target nodes $t_1$, $t_2$, respectively, the concatenation of $D_1$ and $D_2$ is a DAG $D=(V_1\cup V_2,A_1\cup A_2\cup \{(t_1,s_2)\})$. Informally $D$ is obtained by adding an arc from $t_1$ to $s_2$. The definition can be easily extended to more than two DAGs, specifying the order of concatenation. Note that the definition of concatenation holds also for paths.

In this section we present hardness results for the $\mathrm{\Sigma }$-Representing Path and Maximum Representing Path problems. In Subsection 3.1 we show the NP-completeness of the $\mathrm{\Sigma }$-Representing Path problem even if when each symbol labels at most three nodes of $D$, whose degree is bounded by three. In Subsection 3.2 we show two hardness of approximation results for the Maximum Representing Path problem: first we show that the problem is APX-hard even if each symbol labels at most three nodes of $D$, whose degree is bounded by three; then we show a stronger result on arbitrary instances, namely that Maximum Representing Path cannot be approximated within a factor of $\frac{e}{e-1}-\alpha$, for any constant $\alpha >0$, unless $NP\subseteq DTIME({|V|}^{O(\log \log |V|)})$.

In this section we present a polynomial time exact algorithm (Algorithm 1) for the $\mathrm{\Sigma }$-Representing Path problem when each symbol in $\mathrm{\Sigma }$ labels at most two nodes of the input DAG $D$. We first introduce the notion of compatible nodes.

Algorithm 1 reduces the input instance of the $\mathrm{\Sigma }$-Representing Path problem when each symbol labels at most two nodes to an instance of 2-SAT, which is know to be polynomial time solvable [24, 4].

The $\mathrm{\Sigma }$-Representing Path and the Maximum Representing Path problems are trivial if the DAG, after the removal of $s$ and $t$, consists of a set of disjoint paths. Here we consider the two problems when parameterized by distance to disjoint paths and we show that $\mathrm{\Sigma }$-Representing Path and Maximum Representing Path are W[1]-hard for this parameter. The distance to disjoint paths is defined as the minimum number of nodes to be removed from a graph (in this case $D$) such that the resulting graph consists of a set of node disjoint paths (except possibly for $s$ and $t)$. We prove the hardness results by giving a parameterized reduction from the Multicolored Clique problem, defined as follows.

A clique in $G$ that contains exactly one node for each color class is called a multicolored clique. Given an instance $G=(W,E)$ of the Multicolored Clique problem (recall that the partition of $W$ in color classes is given in input), we construct a corresponding instance $(D,\lambda )$ of $\mathrm{\Sigma }$-Representing Path. The DAG $D$ consists of three subgraphs, that share some nodes (see Fig. 3 for a representation of the structure of $D$): (1) a DAG $D_1$ with source node $s_1=s$ and target node $t_1$, (2) A DAG $D_2$ with source node $s_2=t_1$ and target node $t_2$, and (3) A DAG $D_3$ with source node $s_3=t_2$ and target node $t_3=t$.

We first give an informal description of the reduction and then we present it formally. $D_1$ and $D_2$ encode a multicolored clique (symbols not covered by a path in $D_1$ and $D_2$ represent nodes and edges of a multicolored clique), $D_3$ enables to cover all the symbols not selected in $D_1$ and $D_2$ (assuming a path selected in $D_1$ and $D_2$ contains all the symbols except those encoding a multicolored clique).

Consider $G=(W,E)$, where $W=\{w_{1,1},\mathrm{\dots },w_{k,|W_k|}\}$, and $w_{i,h}$, $i\in [k]$ and $h\in [|W_i|]$, represents the $h$-th node of color class $W_i$ (we assume that the nodes in each color class have some ordering). We start by giving an informal description of $D_1$, $D_2$ and $D_3$.

The DAG $D_1$ consists of $k$ concatenated DAGs $D_1^1$, …, $D_1^k$ (see Fig. 4 for a sketch of $D_1^1$), where each $D_1^i$, $i\in [k]$, is associated with a color class $W_i$. Each $D_1^i$, $i\in [k]$, encodes the selection of exactly one node of $W_i$ and it contains a path, denoted by $D_1(w_{i,h})$, for each node $w_{i,h}\in W_i$, with $h\in [|W_i|]$. $D_1^i$ has a source node $s_1^i$ and a target node $t_1^i$. Node $s_1^i$ has arcs to the first node of each path $D_1(w_{i,h})$. Each $D_1(w_{i,h})$ contains the symbols associated with nodes in $W_i$, except for the symbols associated with $w_{i,h}$.

The DAG $D_2$ consists of $k(k-1)$ concatenated DAGs $D_2^{1,2}$, …, $D_2^{k,k-1}$ (see Fig. 5 for a sketch of $D_2^{1,2}$), where each $D_2^{i,j}$, $i,j\in [k]$, $i\ne j$, is associated with edges connecting nodes of color class $W_i$ and color class $W_j$. DAG $D_2^{i,j}$ has a source node $s_2^{i,j}$ and a target node $t_2^{i,j}$. For each edge $\{w_{i,h},w_{j,q}\}\in E$, $h\in [|W_i|]$ and $q\in [|W_j|]$, $D_2^{i,j}$ contains one path, denoted by $D_2(w_{i,h},w_{j,q})$ whose nodes are labeled by one symbol associated with $w_{i,h}$, and set $L_{i,j}$ (encoding edges between nodes of $W_i$ and of $W_j$) except for the symbol associated with edge $\{w_{i,h},w_{j,q}\}$.

The DAG $D_3$ (see Fig. 6) consists of $k$ concatenated DAGs $D_3^1$, …, $D_3^k$, each one associated with a color class $W_i$, $i\in [k]$. Each $D_3^i$, $i\in [k]$, has a source node $s_3^i$ and a target node $t_3^i$. Node $s_3^i$ has arcs to $|W_i|$ paths, one path $D_3(w_{i,h})$ for each node $w_{i,h}\in W_i$, $h\in [|W_i|]$. The nodes in $D_3(w_{i,h})$ have labels that encode $w_{i,h}$ and the edges incident in $w_{i,h}$. The idea is that the symbols not covered by a path in $D_1$ and $D_2$ can be covered by a path in $D_3$ only if the path in $D_1$ and $D_2$ contains all the symbols except those encoding edges of a multicolored clique in $G$ and one symbol for each node in the multicolored clique.

Now, we present the details of the reduction. We start by defining the alphabet $\mathrm{\Sigma }$ and some subsets of $\mathrm{\Sigma }$.

We define sets $B(w_{i,h})$, $w_{i,h}\in W_i$, and $B_i$, $i\in [k]$, of symbols:

Given $i,j\in [k]$, with $i\ne j$, we denote the subset $L_{i,j}$ of symbols as follows:

The set $L_i$, $i\in [k]$, is defined as follows:

Note that $L_{i,j}$ and $L_{j,i}$ are different subsets, in particular that $l_{i,h,j,q}\ne l_{j,q,i,h}$.

Now, we define the DAG $D_1$. $D_1$ has a source node $s_1=s$ and a target node $t_1$, both labeled by $a_1$. $D_1$ is obtained by concatenating DAGs $D_1^i$, $i\in [k]$, each one associated with a color class. Each $D_1^i$ has a source node $s_1^i$ and a target node $t_1^i$. For each $i\in [k-1]$, there exists an arc from $t_1^i$ to $s_1^{i+1}$ (this defines the concatenation of subgraphs $D_1^i$). Now, we define each subgraph $D_1^i$, $i\in [k]$:

• $\mathrm{■}$

  Each subgraph $D_1^i$ has a source node $s_1^i$ and a target node $t_1^i$, labeled by $a_i$.

• $\mathrm{■}$

  Node $s_1^i$ is connected to $|W_i|$ disjoint paths $D_1(w_{i,h})$, each one associated with a node $w_{i,h}\in W_i$.

• $\mathrm{■}$

  Each path $D_1(w_{i,h})$ is labeled by symbols

  $$B_i\setminus \bigcup _{q\in [k]}\{b_{i,h,q}\}$$

Finally, there is an arc from node $s_1$ to $s_1^1$ and an arc from node $t_1^k$ to node $t_1$.

Next, we define the DAG $D_2$. $D_2$ has a source node $s_2=t_1$ and a target node $t_2$, both labeled by symbol $a_2$. $D_2$ is obtained by concatenating DAGs $D_2^{i,j}$, with $i,j\in [k]$ and $i\ne j$, each one associated with $W_i$ and $W_j$. Each $D_2^{i,j}$ has a source node $s_2^{i,j}$ and a target node $t_2^{i,j}$. We assume that DAGs $D_2^{i,j}$ are concatenated as follows: for $i,j\in [k]$ with $i\ne j$, if then there is an arc from the target $t_2^{i,j}$ of $D_2^{i,j}$ to the source $s_2^{i,j+1}$ of $D_2^{i,j+1}$, and if $j=k$ (and ) there is an arc from the source $s_2^{i,j}$ of $D_2^{i,j}$ to the target $t_2^{i+1,1}$ of $D_2^{i+1,1}$.

Now, we define each subgraph $D_2^{i,j}$, $i,j\in [k]$ and $i\ne j$:

• $\mathrm{■}$

  Each subgraph $D_2^{i,j}$ has a source node $s_2^{i,j}$ and a target node $t_2^{i,j}$, labeled by $a_i$.

• $\mathrm{■}$

  Node $s_2^{i,j}$ is connected to paths $D_2(w_{i,h},w_{j,q})$, each one associated with a node $w_{i,h}\in W_i$ and a node $w_{j,q}\in W_j$, such that $\{w_{i,h},w_{j,q}\}\in E$.

• $\mathrm{■}$

  Each path $D_2(w_{i,h},w_{j,q})$ is labeled by the set of symbols (recall that $i\ne j$, hence symbol $b_{i,h,i}$ does not label any node on each path $D_2(w_{i,h},w_{j,q})$):

  $$(L_{i,j}\cup \{b_{i,h,j}\})\setminus \{l_{i,h,j,q}\}$$

Finally, there is an arc from node $s_2$ to $s_2^{1,2}$ and an arc from node $t_2^{k,k-1}$ to node $t_2$.

Now, we define the DAG $D_3$. $D_3$ has source $s_3$ and target $t_3$, both labeled by $a_3$. $D_3$ is obtained by concatenating DAGs $D_3^i$, $i\in [k]$, each one associated with a color class. Each subgraph $D_3^i$, $i\in [k]$, is defined as follows:

• $\mathrm{■}$

  Each subgraph $D_3^i$ has a source node $s_3^i$ and a target node $t_3^i$, labeled by $a_i$.

• $\mathrm{■}$

  Between nodes $s_3^i$ and $t_3^i$ there are $|W_i|$ disjoint paths, $D_3(w_{i,h})$, $h\in [|W_i|]$, each one associated with a node $w_{i,h}\in W_i$.

• $\mathrm{■}$

  The nodes in each path $D_3(w_{i,h})$ are labeled by the following set of symbols

  $$\bigcup _{\{w_{i,h},w_{j,q}\}\in E}\{l_{j,q,i,h}\}\cup \{b_{i,h,i}\}.$$

Note that the path $D_3(w_{i,h})$ contains nodes having labels $\{l_{j,q,i,h}\}$ that encode edges of $E$ incident in $w_{i,h}$. Note also that these nodes, for each edge $\{w_{i,h},w_{j,q}\}\in E$, have labels $\{l_{j,q,i,h}\}$ not $\{l_{i,h,j,q}\}$.

Finally, there is an arc from $t_3^i$ to $s_3^{i+1}$, with $i\in [k-1]$, an arc from $s_3$ (the source of $D_3$) to $s_3^1$ and an arc from $t_3^k$ to $t_3$.

Having defined $D$ and its labeling, we start to prove some properties of graph $D_1$ and $D_2$.

In this section we present a polynomial time approximation algorithm for the Maximum Representing Path problem that achieves an approximation factor of $\sqrt{OPT}$, where $OPT$ is the number of distinct symbols in an optimal solution. Notice that, since $OPT\le |\mathrm{\Sigma }|$, our algorithm is also a $\sqrt{|\mathrm{\Sigma }|}$-approximation. Informally, the algorithm is as follows. First, we create a compatibility DAG $D^{\prime }=(V^{\prime },A^{\prime })$, that is essentially the transitive closure of the input DAG $D$ (see Section 2 for the definition of transitive closure). Then, we consider a total order on $\mathrm{\Sigma }$, e.g., standard alphabetic order, such that we have , for two nodes $u$ and $v$ if the label of $u$ precedes the label of $v$ based on this order. We create two subgraphs of $D^{\prime }$ (that are implicitly DAGs), $D^1$ and $D^2$ as follows:

1. 1.

   $D^1=(V,A^1)$ where $(v_1,v_2)\in A^1$ if and only if $(v_1,v_2)\in A^{\prime }$ and
   

2. 2.

   $D^2=(V,A^2)$ where $(v_1,v_2)\in A^2$ if and only if $(v_1,v_2)\in A^{\prime }$ and $\lambda (v_1)>\lambda (v_2)$.

Observe that $A^1,A^2\subseteq A$ and that the set of nodes of $D^1$ and $D^2$ is $V$. We then compute $p_1$, a longest path between $s$ and $t$ in $D^1$, and $p_2$, a longest path between $s$ and $t$ in $D^2$. As pointed out in Section 2, a longest path in a DAG can be computed in linear time. The algorithm (formally presented in Algorithm 2) outputs the path $p_i$, $i\in \{1,2\}$, that has a largest number of distinct symbols. Theorem 11 proves that it is indeed a $\sqrt{OPT}$-approximation for Maximum Representing Path.

In this contribution we have introduced two combinatorial problems ($\mathrm{\Sigma }$-Representing Path and Maximum Representing Path) that ask to identify a path in a node labeled DAG that contains all (or a subset of maximum size) of the alphabet symbols. We have proved results on the computational complexity and parameterized complexity of the two problems, and we have studied the approximation of Maximum Representing Path.

One of the most interesting future directions is to further investigate the approximate complexity of the Maximum Representing Path problem: does it admit constant factor approximation algorithms? It is interesting to design approximation algorithms for some restrictions on the DAG structure, for example when the degree is bounded. It is also interesting to study other structural properties of the DAG that may lead to polynomial-time algorithms for both problems.