1. Faster exact algorithms for some terminal set problems.
- Author
-
Chitnis, Rajesh, Fomin, Fedor V., Lokshtanov, Daniel, Misra, Pranabendu, Ramanujan, M.S., and Saurabh, Saket
- Subjects
- *
GRAPH theory , *ALGORITHMS , *SET theory , *PROBLEM solving , *PATHS & cycles in graph theory - 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 ⁎ ( 2 n ) barrier for the classic Node Multiway Cut , Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF