Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951160 | Journal of Computer and System Sciences | 2017 | 13 Pages |
Abstract
Many problems on graphs can be expressed in the following language: given a graph G=(V,E) and a terminal set TâV, find a minimum size set SâV which intersects all “structures” (such as cycles or paths) passing through the vertices in T. We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the Oâ(2n) barrier for the classic Node Multiway Cut, Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M.S. Ramanujan, Saket Saurabh,