## Abstract

A 2-partition of a digraph D is a partition (V_{1},V_{2}) of V(D) into two disjoint non-empty sets V_{1} and V_{2} such that V_{1}∪V_{2}=V(D). A semicomplete digraph is a digraph with no pair of non-adjacent vertices. We consider the complexity of deciding whether a given semicomplete digraph has a 2-partition such that each part of the partition induces a (semicomplete) digraph with some specified property. In [4] and [5] Bang-Jensen, Cohen and Havet determined the complexity of 120 such 2-partition problems for general digraphs. Several of these problems are NP-complete for general digraphs and thus it is natural to ask whether this is still the case for well-structured classes of digraphs, such as semicomplete digraphs. This is the main topic of the paper. More specifically, we consider 2-partition problems where the set of properties are minimum out-, minimum in- or minimum semi-degree. Among other results we prove the following: • For all integers k_{1},k_{2}≥1 and k_{1}+k_{2}≥3 it is NP-complete to decide whether a given digraph D has a 2-partition (V_{1},V_{2}) such that D〈V_{i}〉 has out-degree at least k_{i} for i=1,2.• For every fixed choice of integers α,k_{1},k_{2}≥1 there exists a polynomial algorithm for deciding whether a given digraph of independence number at most α has a 2-partition (V_{1},V_{2}) such that D〈V_{i}〉 has out-degree at least k_{i} for i=1,2.• For every fixed integer k≥1 there exists a polynomial algorithm for deciding whether a given semicomplete digraph has a 2-partition (V_{1},V_{2}) such that D〈V_{1}〉 has out-degree at least one and D〈V_{2}〉 has in-degree at least k.• It is NP-complete to decide whether a given semicomplete digraph D has a 2-partition (V_{1},V_{2}) such that D〈V_{i}〉 is a strong tournament.

Original language | English |
---|---|

Journal | Theoretical Computer Science |

Volume | 746 |

Pages (from-to) | 112-123 |

ISSN | 0304-3975 |

DOIs | |

Publication status | Published - 25. Oct 2018 |

## Keywords

- 2-partition
- Digraphs of bounded independence number
- Minimum in-degree
- Minimum out-degree
- Minimum semi-degree
- NP-complete
- Semicomplete digraph
- Tournament