| Title | : | Longest Path, Reachability and Max-poly Weighting Schemes |
| Speaker | : | Devakar Kumar Verma (IITM) |
| Details | : | Tue, 24 Mar, 2015 2:00 PM @ BSB 361 |
| Abstract: | : | he Longest Path problem on graphs is an important problem in the context of computational
complexity theory. The problem is NP-complete for general graphs, while for directed acyclic
graphs, it has a polynomial-time algorithm, and it has important implications for scheduling problems. For smaller subclasses of graphs, the problem has interesting implications in relation to space complexity classes.
A weighting scheme on a graph G(V;E), is an assignment of non-negative weights to each edge e in E. A weighting scheme is called max-unique with respect to a source vertex s, if for every vertex v in V , there is at most one path of maximum weight from s to v in G. Limaye, Mahajan and Nimbhorkar (2009) proposed an unambiguous non-deterministic log-space algorithm which solves the Longest Path Problem on max-unique DAGs with a unique sink. As our main contribution, we improve this result relaxing the restriction of maximum-weight-paths from unique to polynomially many. We do this by employing a three variable inductive counting technique combined with a method of verifying unambiguously. As a main application of our result, we give a reduction from the Reachability problem on general weighted DAGs to the Longest Path problem on single-sink DAGs, while preserving the max-unique/max-poly property of the weighting scheme of the graph. A consequence of this result is that it suffices to construct a max-poly weighting scheme for DAGs to show that NL = UL. |
