Faster exact algorithms for some terminal set problems

Rajesh Chitnis; Fedor V. Fomin; Daniel Lokshtanov; Pranabendu Misra; M. S. Ramanujan; Saket Saurabh

doi:10.1016/j.jcss.2017.04.003

Faster exact algorithms for some terminal set problems

Rajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan^*, Saket Saurabh

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

216 Downloads (Pure)

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ⁿ) barrier for the classic NODE MULTIWAY CUT, DIRECTED UNRESTRICTED NODE MULTIWAY CUT and DIRECTED SUBSET FEEDBACK VERTEX SET problems.

Original language	English
Pages (from-to)	195-207
Number of pages	13
Journal	Journal of Computer and System Sciences
Volume	88
Issue number	September
Early online date	4 May 2017
DOIs	https://doi.org/10.1016/j.jcss.2017.04.003
Publication status	Published - 1 Sept 2017

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.jcss.2017.04.003Licence: None: All rights reserved

Chitnis_et_al_Faster_exact_algorithms_JCSS_2017Accepted author manuscript, 348 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

https://www.sciencedirect.com/science/article/pii/S0022000017300569Licence: None: All rights reserved

Cite this

@article{757d221d388649dcb099787f53afd62a,

title = "Faster exact algorithms for some terminal set problems",

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 = "Exact exponential time algorithms, Feedback vertex set, Multiway cut, Terminal set problems",

author = "Rajesh Chitnis and Fomin, {Fedor V.} and Daniel Lokshtanov and Pranabendu Misra and Ramanujan, {M. S.} and Saket Saurabh",

year = "2017",

month = sep,

day = "1",

doi = "10.1016/j.jcss.2017.04.003",

language = "English",

volume = "88",

pages = "195--207",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Elsevier",

number = "September",

}

TY - JOUR

T1 - Faster exact algorithms for some terminal set problems

AU - Chitnis, Rajesh

AU - Fomin, Fedor V.

AU - Lokshtanov, Daniel

AU - Misra, Pranabendu

AU - Ramanujan, M. S.

AU - Saurabh, Saket

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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.

AB - 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.

KW - Exact exponential time algorithms

KW - Feedback vertex set

KW - Multiway cut

KW - Terminal set problems

UR - http://www.scopus.com/inward/record.url?scp=85020254879&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2017.04.003

DO - 10.1016/j.jcss.2017.04.003

M3 - Article

AN - SCOPUS:85020254879

SN - 0022-0000

VL - 88

SP - 195

EP - 207

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - September

ER -

Faster exact algorithms for some terminal set problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this