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^*

^*Corresponding author for this work

Department of Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

57 Downloads (Pure)

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
Journal	Theoretical Computer Science
Volume	844
Pages (from-to)	97-105
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2020.08.008
Publication status	Published - 6. Dec 2020

Keywords

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

Documents & Links

10.1016/j.tcs.2020.08.008

Open Access VersionSubmitted manuscript, 174 KB

Cite this

@article{5d74391842a34616bce2cd50823946a4,

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 V 1,V 2 such that the digraph D[V 1] induced by V 1 has a vertex that can reach all other vertices by directed paths, the digraph D[V 2] has no vertex of in-degree zero and |V i|≥k i, where k 1,k 2 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 = "J.B. Andersen and J. Bang-Jensen and A. Yeo",

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",

}

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 V 1,V 2 such that the digraph D[V 1] induced by V 1 has a vertex that can reach all other vertices by directed paths, the digraph D[V 2] has no vertex of in-degree zero and |V i|≥k i, where k 1,k 2 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 V 1,V 2 such that the digraph D[V 1] induced by V 1 has a vertex that can reach all other vertices by directed paths, the digraph D[V 2] has no vertex of in-degree zero and |V i|≥k i, where k 1,k 2 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

U2 - 10.1016/j.tcs.2020.08.008

DO - 10.1016/j.tcs.2020.08.008

M3 - Journal article

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

Documents & Links

Fingerprint

Cite this