Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard

Michał Włodarczyk

In the Disjoint Paths problem, one is given a graph with a set of $k$ vertex pairs $(s_i,t_i)$ and the task is to connect each $s_i$ to $t_i$ with a path, so that the $k$ paths are…