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

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

1 Downloads (Pure)

Abstrakt

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

Originalsprog	Engelsk
Tidsskrift	Theoretical Computer Science
ISSN	0304-3975
DOI	https://doi.org/10.1016/j.tcs.2020.08.008
Status	E-pub ahead of print - 14. aug. 2020

Dokumenter og links

10.1016/j.tcs.2020.08.008

Open Access VersionIndsendt manuskript, 174 KB

Fingeraftryk Dyk ned i forskningsemnerne om 'On the parameterized complexity of 2-partitions'. Sammen danner de et unikt fingeraftryk.

Citationsformater

Andersen, J. B., Bang-Jensen, J., & Yeo, A. (2020). On the parameterized complexity of 2-partitions. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2020.08.008

@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 = aug,

day = "14",

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

language = "English",

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/8/14

Y1 - 2020/8/14

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

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -