1
$\begingroup$

Let $D=(V,A)$ be a simple directed acyclic graph, where $A$ is a set of arcs. Let $S$ be a subset of $\{(u,v)| \text{there is a directed path from $u$ to $v$}\}$. The $S$-length of a path $P$ is defined to be the number of elements of $S$ contained in $P$, here $(u,v)\in S$ is said to be contained in $P$ if $u,v \in V(P)$. For example, if $S =\{(u,v)| \text{there is a directed path from $u$ to $v$}\}$, then length of a path $P$ is ${L(P)}\choose{2}$ where $L(P)$ is the length of the path $P$. My question is to find a path of longest $S$-length in $D$. Is there a polynomial algorithm to solve it? If it is NP-hard, then is there a good approximation algorithm?

I am so sorry I realized there is a mistake in my old question. Here $S$ is a subset of $V\times V$,i.e, a subset of all pairs of vertices, but $S$ is not a subset of $A$.

Improve this question
$\endgroup$
7
  • $\begingroup$ Small nitpick: '(NP-hard)' is not known to be the the negation of '$\exists$polynomial algorithm'. The phrasing of the OP, with the "Or, if" makes it sound a bit as it it was. I would recommed to replace "Or, if it..." with simply "If it...". I shied away from making this invasive edit. $\endgroup$
    – Peter Heinig
    Commented Feb 13, 2018 at 10:55
  • 1
    $\begingroup$ Dear Peter, thanks for your suggestion! $\endgroup$
    – Moshe
    Commented Feb 13, 2018 at 10:56
  • $\begingroup$ Do binary search on powers of the adjacency matrix. $\endgroup$
    – Steve Huntsman
    Commented Feb 13, 2018 at 11:03
  • $\begingroup$ @Ethan Is there polynomial or exponential number of maximal path in DAG? $\endgroup$
    – Moshe
    Commented Feb 13, 2018 at 11:07
  • $\begingroup$ @Moshe I misinterpreted your problem, discount what I previously said. $\endgroup$
    – Ethan Splaver
    Commented Feb 13, 2018 at 14:38

2 Answers 2

Reset to default
2
$\begingroup$

It’s NP-hard to approximate this within any constant factor, by a reduction from 2-CSP (that it is hard to approximate 2-CSP follows from the PCP theorem and parallel repetition). Suppose I have an instance of 2-CSP with variables $x_1, ..., x_n$ taking values in the alphabet $\Sigma$, and constraints $C_{i,j} \subseteq \Sigma \times \Sigma$ for certain pairs $i,j$ between $1$ and $n$. Make a directed graph $(V, A)$ with $V = \{v_{i,a} : i \le n, a \in \Sigma\}$ and $A = \{(v_{i,a}, v_{i+1,b}) : i \le n-1, a,b \in \Sigma\}$. For each constraint $C_{i,j}$ (assuming $i$ less than $j$ without loss of generality), we include the pairs $(v_{i,a},v_{j,b})$ such that $(a,b) \in C_{i,j}$ in the set $S$. Then any maximal path corresponds to an assignment of the variables to elements of $\Sigma$, and the $S$-length is equal to the number of satisfied constraints.

Improve this answer
$\endgroup$
0
$\begingroup$

The wikipedia page on longest path problems gives an efficient algorithm to find longest paths in directed acyclic graphs:

https://en.wikipedia.org/wiki/Longest_path_problem

If you adapt this algorithm by weighting arcs 1 if they lie in S, and 0 otherwise, this gives the algorithm you want.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dear Simon, thank you for your answer. There is a mistake in my previous question and I have just changed it. I am really sorry! $\endgroup$
    – Moshe
    Commented Feb 13, 2018 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .