On the parameterized complexity of 2-partitions

2020/03/16 by Jonas Bamse Andersen, Andersen, Jonas Bamse, Jørgen Bang‐Jensen +3
Computer Science · Engineering · Mathematics · #05C20 #Advanced Graph Theory Research #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2003.07190

openalex publication_date 2020/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an FPT algorithm for deciding whether the vertex set 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].

Citations

• Complexity of acyclic colorings of graphs and digraphs with degree and\n girth constraints

Related

• Out-degree reducing partitions of digraphs
• Degree-constrained 2-partitions of graphs
• The Satisfactory Partition Problem
• Bipartite spanning sub(di)graphs induced by 2-partitions
• Revisiting Directed Disjoint Paths on tournaments (and relatives)