On the parameterized complexity of 2-partitions

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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

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

Original languageEnglish
JournalTheoretical Computer Science
Volume844
Pages (from-to)97-105
ISSN0304-3975
DOIs
Publication statusPublished - 6. Dec 2020

Keywords

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

Fingerprint

Dive into the research topics of 'On the parameterized complexity of 2-partitions'. Together they form a unique fingerprint.

Cite this