English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For a given $2$-partition $(V_1,V_2)$ of the vertices of a (di)graph $G$, westudy properties of the spanning bipartite subdigraph $B_G(V_1,V_2)$ of $G$induced by those arcs/edges that have one end in each $V_i$. We determine, forall pairs of non-negative integers $k_1,k_2$, the complexity of decidingwhether $G$ has a 2-partition $(V_1,V_2)$ such that each vertex in $V_i$ has atleast $k_i$ (out-)neighbours in $V_{3-i}$. We prove that it is ${\calNP}$-complete to decide whether a digraph $D$ has a 2-partition $(V_1,V_2)$such that each vertex in $V_1$ has an out-neighbour in $V_2$ and each vertex in$V_2$ has an in-neighbour in $V_1$. The problem becomes polynomially solvableif we require $D$ to be strongly connected. We give a characterisation, basedon the so-called strong component digraph of a non-strong digraph of thestructure of ${\cal NP}$-complete instances in terms of their strong componentdigraph. When we want higher in-degree or out-degree to/from the other set theproblem becomes ${\cal NP}$-complete even for strong digraphs. A further resultis that it is ${\cal NP}$-complete to decide whether a given digraph $D$ has a$2$-partition $(V_1,V_2)$ such that $B_D(V_1,V_2)$ is strongly connected. Thisholds even if we require the input to be a highly connected eulerian digraph.

Bipartite spanning sub(di)graphs induced by 2-partitions