On the parameterized complexity of 2-partitions

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

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

73 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 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
Vol/bind844
Sider (fra-til)97-105
ISSN0304-3975
DOI
StatusUdgivet - 6. dec. 2020

Fingeraftryk

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

Citationsformater