Improved parameterized and exact algorithms for cut problems on trees

Iyad Kanj; Guohui Lin; Tian Liu; Weitian Tong; Ge Xia; Jinhui Xu; Boting Yang; Fenghui Zhang; Peng Zhang; Binhai Zhu

doi:10.1016/j.tcs.2015.06.010

Improved parameterized and exact algorithms for cut problems on trees

Iyad Kanj, Guohui Lin, Tian Liu, Weitian Tong, Ge Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang, Binhai Zhu

Computer Science

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

4 Scopus citations

Abstract

We study the MULTICUT ON TREES and the GENERALIZED MULTIWAY CUT ON TREES problems. For the MULTICUT ON TREES problem, we present a parameterized algorithm that runs in time O^⁎(ρ^k), where ρ=2+1<1.554 is the positive root of the polynomial x⁴−2x²−1. This improves the current-best algorithm of Chen et al. that runs in time O^⁎(1.619^k). For the GENERALIZED MULTIWAY CUT ON TREES problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the GENERALIZED MULTIWAY CUT ON TREES problem to the MULTICUT ON TREES problem, our results give a parameterized algorithm that solves the GENERALIZED MULTIWAY CUT ON TREES problem in time O^⁎(ρ^k).

Original language	English
Pages (from-to)	455-470
Number of pages	16
Journal	Theoretical Computer Science
Volume	607
DOIs	https://doi.org/10.1016/j.tcs.2015.06.010
State	Published - Nov 1 2015

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Keywords

Exact algorithm
Multicut
Multiway cut
Parameterized algorithm
Tree

Access to Document

10.1016/j.tcs.2015.06.010

Cite this

@article{eb8cd1c9ee914abba3d452bacacb702d,

title = "Improved parameterized and exact algorithms for cut problems on trees",

abstract = "We study the MULTICUT ON TREES and the GENERALIZED MULTIWAY CUT ON TREES problems. For the MULTICUT ON TREES problem, we present a parameterized algorithm that runs in time O⁎(ρk), where ρ=2+1<1.554 is the positive root of the polynomial x4−2x2−1. This improves the current-best algorithm of Chen et al. that runs in time O⁎(1.619k). For the GENERALIZED MULTIWAY CUT ON TREES problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the GENERALIZED MULTIWAY CUT ON TREES problem to the MULTICUT ON TREES problem, our results give a parameterized algorithm that solves the GENERALIZED MULTIWAY CUT ON TREES problem in time O⁎(ρk).",

keywords = "Exact algorithm, Multicut, Multiway cut, Parameterized algorithm, Tree",

author = "Iyad Kanj and Guohui Lin and Tian Liu and Weitian Tong and Ge Xia and Jinhui Xu and Boting Yang and Fenghui Zhang and Peng Zhang and Binhai Zhu",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = nov,

day = "1",

doi = "10.1016/j.tcs.2015.06.010",

language = "English",

volume = "607",

pages = "455--470",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Improved parameterized and exact algorithms for cut problems on trees

AU - Kanj, Iyad

AU - Lin, Guohui

AU - Liu, Tian

AU - Tong, Weitian

AU - Xia, Ge

AU - Xu, Jinhui

AU - Yang, Boting

AU - Zhang, Fenghui

AU - Zhang, Peng

AU - Zhu, Binhai

PY - 2015/11/1

Y1 - 2015/11/1

N2 - We study the MULTICUT ON TREES and the GENERALIZED MULTIWAY CUT ON TREES problems. For the MULTICUT ON TREES problem, we present a parameterized algorithm that runs in time O⁎(ρk), where ρ=2+1<1.554 is the positive root of the polynomial x4−2x2−1. This improves the current-best algorithm of Chen et al. that runs in time O⁎(1.619k). For the GENERALIZED MULTIWAY CUT ON TREES problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the GENERALIZED MULTIWAY CUT ON TREES problem to the MULTICUT ON TREES problem, our results give a parameterized algorithm that solves the GENERALIZED MULTIWAY CUT ON TREES problem in time O⁎(ρk).

AB - We study the MULTICUT ON TREES and the GENERALIZED MULTIWAY CUT ON TREES problems. For the MULTICUT ON TREES problem, we present a parameterized algorithm that runs in time O⁎(ρk), where ρ=2+1<1.554 is the positive root of the polynomial x4−2x2−1. This improves the current-best algorithm of Chen et al. that runs in time O⁎(1.619k). For the GENERALIZED MULTIWAY CUT ON TREES problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the GENERALIZED MULTIWAY CUT ON TREES problem to the MULTICUT ON TREES problem, our results give a parameterized algorithm that solves the GENERALIZED MULTIWAY CUT ON TREES problem in time O⁎(ρk).

KW - Exact algorithm

KW - Multicut

KW - Multiway cut

KW - Parameterized algorithm

KW - Tree

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

U2 - 10.1016/j.tcs.2015.06.010

DO - 10.1016/j.tcs.2015.06.010

M3 - Article

AN - SCOPUS:84984863705

SN - 0304-3975

VL - 607

SP - 455

EP - 470

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Improved parameterized and exact algorithms for cut problems on trees

Abstract

Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this