## Compressing and summarizing. Part 3.

[Disclaimer: this a blog-post consciously written in the style adumbrated in Compressing and summarizing. Part 0. For the original, see https://arxiv.org/abs/1707.09400. Compression ratio here is high. ]

This recent preprint of Jørgen Bang-Jensen, Stéphane Bessy, Frédéric Havet, Anders Yeo on digraphs is very interesting to me, because

• I am recently quite involved in digraph-theory for more than one reason,
• since student-days I am very interested  in max-cut-like problems like the folklore classic recalled in Prop. 1. of loc. cit.

so I’ll here report on loc.cit.

For further reference, we introduce notation:

• Let $\mathsf{BipDgr}$ denote the full subcategory of the category $\mathsf{Dgr}$ of digraphs which is spanned by the bipartite digraphs. For each digraph $D$ let $\mathsf{BipDgr}(D)$ denote the full subcategory of $\mathsf{BigDgr}$ spanned by the spanning bipartite subdigraphs of $D$. Let $2^V$ denote the power-set of the set $V$, considered as a posetal category in the usual way.    Central concept of loc. cit. is, for each digraph $D=(V,A)$, a functor

$F(D)\colon 2^V\rightarrow\mathsf{BipDg}(D)$

which in particular takes any $U\subseteq V$ to digraph $(V,\{ (x,y)| x\in U, y\in V\setminus U, (x,y)\in A \})$.

Graph here means undirected simple graph.

For brevity,

• ‘isol.-free.’ is an abbreviation for ‘is free of isolated vertices'($=$has minimum degree at least one),
• $(d_0,d_1)$-bipartition’ is an abbreviation for ‘bipartition $V = V_0\sqcup V_1$ of the vertex set of the graph such that each vertex in $V_i$ has at least $d_i$ neighbours in $V_{1-i}$. Loc. cit. Problem 2 denotes this by the longer ‘$(\delta\geq k_1 , \delta\geq k_2)$-bipartite partition’.

On a pedantic note, it seems an improvement to replace the formulation ‘bipartite-partition’ of loc. cit. with ‘bipartition’, since strictly speaking a ‘bipartite partition’ is not defined in graph theory, and since my alternative suggestion is even shorter than the original.

Prop. 1 loc. cit. recalls the fact that every finite graph admits an unfriendly partition. Loc. cit. then points out that this implies that every finite isol.-free graph admits a partition such that the bipartite graph defined by it is itself isol.-free. This of course implies that there is a time $O(n)$ algorithm to decide if an $n$-vertex graph admits a $(1,1)$-bipartition.

Loc. cit. then states the more general class of decision problems

• $(d_0,d_1)$$\mathsf{BIPAR}$ $\equiv$ given a finite graph, to decide whether it admits at least one $(d_0,d_1)$-bipartition.

Loc. cit. inter alia gives a proof that

• if $d_0+d_1\leq 3$, then $(d_0,d_1)$$\mathsf{BIPAR}$ admits an algorithm polynomial in the order of the input graph,
• if $d_0+d_1\geq 4$, then $(d_0,d_1)$$\mathsf{BIPAR}$ is NP-complete.

To be continued.