On the parameterized complexity of 2-partitions

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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 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].

OriginalsprogEngelsk
TidsskriftTheoretical Computer Science
ISSN0304-3975
DOI
StatusE-pub ahead of print - 14. aug. 2020

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

  • Citationsformater