Faster exact algorithms for some terminal set problems

Research output: Contribution to journalArticle

Authors

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Pranabendu Misra
  • M. S. Ramanujan
  • Saket Saurabh

Colleges, School and Institutes

External organisations

  • University of Bergen
  • HBNI, Chennai, India

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.

Details

Original languageEnglish
Pages (from-to)195-207
Number of pages13
JournalJournal of Computer and System Sciences
Volume88
Issue numberSeptember
Early online date4 May 2017
Publication statusPublished - 1 Sep 2017

Keywords

  • Exact exponential time algorithms, Feedback vertex set, Multiway cut, Terminal set problems