## Abstract

For a given (Formula presented.) -partition (Formula presented.) of the vertices of a (di)graph (Formula presented.), we study properties of the spanning bipartite subdigraph (Formula presented.) of (Formula presented.) induced by those arcs/edges that have one end in each (Formula presented.). We determine, for all pairs of nonnegative integers (Formula presented.), the complexity of deciding whether (Formula presented.) has a 2-partition (Formula presented.) such that each vertex in (Formula presented.) (for (Formula presented.)) has at least (Formula presented.) (out-)neighbours in (Formula presented.). We prove that it is (Formula presented.) -complete to decide whether a digraph (Formula presented.) has a 2-partition (Formula presented.) such that each vertex in (Formula presented.) has an out-neighbour in (Formula presented.) and each vertex in (Formula presented.) has an in-neighbour in (Formula presented.). The problem becomes polynomially solvable if we require (Formula presented.) to be strongly connected. We give a characterisation of the structure of (Formula presented.) -complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set, the problem becomes (Formula presented.) -complete even for strong digraphs. A further result is that it is (Formula presented.) -complete to decide whether a given digraph (Formula presented.) has a (Formula presented.) -partition (Formula presented.) such that (Formula presented.) is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph.

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

Journal | Journal of Graph Theory |

Volume | 92 |

Issue number | 2 |

Pages (from-to) | 130-151 |

ISSN | 0364-9024 |

DOIs | |

Publication status | Published - Oct 2019 |

## Keywords

- 2-partition, spanning bipartite subdigraph
- eulerian
- minimum out-degree
- strong spanning subdigraph