On the parameterized complexity of 2-partitions

DOI10.1016/J.TCS.2020.08.008MaRDI QIDQ2205943zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 October 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.07190

zbMATH Keywords

2-partitiondirected graphFPT algorithmout-branchingparameterized complexity

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We give an FPT algorithm for deciding whether the vertex set 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|geq{k}_i$, where $k_1,k_2$ are part of the input. This settles an open problem from[1,4].

Recommendations

• The parameterized complexity landscape of finding 2-partitions of digraphs
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Degree constrained 2-partitions of semicomplete digraphs
• Partitioning vertices into in- and out-dominating sets in digraphs

Cites work

• A linear algorithm for bipartition of biconnected graphs
• Digraphs
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Finding good 2-partitions of digraphs. II. Enumerable properties
• FPT algorithms for connected feedback vertex set
• On the complexity of partitioning a graph into a few connected subgraphs
• On the girth of digraphs
• Partitioning graphs into connected parts
• Partitions of graphs with high minimum degree or connectivity.
• The circular chromatic number of a digraph
• The parameterized complexity landscape of finding 2-partitions of digraphs
• Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz

Cited in

(4)

• The computational complexity of disconnected cut and \(2 K_2\)-partition
• The parameterized complexity landscape of finding 2-partitions of digraphs
• Parameterized complexity of DAG partitioning
• On the complexity of minimizing energy consumption of partitioning DAG tasks

This page was built for publication: On the parameterized complexity of 2-partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2205943)