On the parameterized complexity of 2-partitions

J. B. Andersen; J. Bang-Jensen; A. Yeo

doi:10.1016/j.tcs.2020.08.008

On the parameterized complexity of 2-partitions

J. B. Andersen, J. Bang-Jensen, A. Yeo

University of Southern Denmark

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

1 Citation (Scopus)

Abstract

We give an FPT algorithm for deciding whether the vertex set of a digraph D can be partitioned into two disjoint sets V₁,V₂ such that the digraph D[V₁] induced by V₁ has a vertex that can reach all other vertices by directed paths, the digraph D[V₂] has no vertex of in-degree zero and |V_i|≥k_i, where k₁,k₂ are part of the input. This settles an open problem from [1,4].

Original language	English
Pages (from-to)	97-105
Number of pages	9
Journal	Theoretical Computer Science
Volume	844
DOIs	https://doi.org/10.1016/j.tcs.2020.08.008
Publication status	Published - 6 Dec 2020
Externally published	Yes

Keywords

2-partition
Directed graph
FPT algorithm
Out-branching
Parameterized complexity

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2020.08.008

Cite this

@article{8b6417729aa44d75b3bfab3f71a61c57,

title = "On the parameterized complexity of 2-partitions",

abstract = "We give an FPT algorithm for deciding whether the vertex set of a digraph D can be partitioned into two disjoint sets V1,V2 such that the digraph D[V1] induced by V1 has a vertex that can reach all other vertices by directed paths, the digraph D[V2] has no vertex of in-degree zero and |Vi|≥ki, where k1,k2 are part of the input. This settles an open problem from [1,4].",

keywords = "2-partition, Directed graph, FPT algorithm, Out-branching, Parameterized complexity",

author = "Andersen, \{J. B.\} and J. Bang-Jensen and A. Yeo",

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

year = "2020",

month = dec,

day = "6",

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

language = "English",

volume = "844",

pages = "97--105",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On the parameterized complexity of 2-partitions

AU - Andersen, J. B.

AU - Bang-Jensen, J.

AU - Yeo, A.

PY - 2020/12/6

Y1 - 2020/12/6

N2 - We give an FPT algorithm for deciding whether the vertex set of a digraph D can be partitioned into two disjoint sets V1,V2 such that the digraph D[V1] induced by V1 has a vertex that can reach all other vertices by directed paths, the digraph D[V2] has no vertex of in-degree zero and |Vi|≥ki, where k1,k2 are part of the input. This settles an open problem from [1,4].

AB - We give an FPT algorithm for deciding whether the vertex set of a digraph D can be partitioned into two disjoint sets V1,V2 such that the digraph D[V1] induced by V1 has a vertex that can reach all other vertices by directed paths, the digraph D[V2] has no vertex of in-degree zero and |Vi|≥ki, where k1,k2 are part of the input. This settles an open problem from [1,4].

KW - 2-partition

KW - Directed graph

KW - FPT algorithm

KW - Out-branching

KW - Parameterized complexity

UR - https://www.scopus.com/pages/publications/85089682297

U2 - 10.1016/j.tcs.2020.08.008

DO - 10.1016/j.tcs.2020.08.008

M3 - Article

AN - SCOPUS:85089682297

SN - 0304-3975

VL - 844

SP - 97

EP - 105

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

On the parameterized complexity of 2-partitions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this