On finding the longest antisymmetric path in directed acyclic graphs

摘要

Given a directed acyclic graph and a set of vertex pairs, an antisymmetric path is a directed path that does not contain vertices from the same pair in the set. The goal of the Longest Antisymmetric Path problem is to determine the longest antisymmetric path that connects two given vertices in the graph. The problem has important applications in software testing and bioinformatics. The problem is known to be NP-hard. In this paper, we study the computational lower bound of the problem, we show that the problem cannot be solved in time 2~(o(n~(1/3))) unless 3SAT can be solved in subexponential time. In addition, we study the inapproximability of the problem and show that the problem cannot be approximated within a ratio of (n-2)/2 in polynomial time unless P = NP. Our technique also suggests that both the lower bound and inapproximability also hold for directed acyclic graphs of degree at most 6.