[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 denote the full subcategory of the category of digraphs which is spanned by the bipartite digraphs. For each digraph let denote the full subcategory of spanned by the spanning bipartite subdigraphs of . Let denote the power-set of the set , considered as a posetal category in the usual way. Central concept of loc. cit. is, for each digraph , a functor
which in particular takes any to digraph .
Graph here means undirected simple graph.
- ‘isol.-free.’ is an abbreviation for ‘is free of isolated vertices'(has minimum degree at least one),
- ‘-bipartition’ is an abbreviation for ‘bipartition of the vertex set of the graph such that each vertex in has at least neighbours in . Loc. cit. Problem 2 denotes this by the longer ‘-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 algorithm to decide if an $n$-vertex graph admits a -bipartition.
Loc. cit. then states the more general class of decision problems
- – given a finite graph, to decide whether it admits at least one -bipartition.
Loc. cit. inter alia gives a proof that
- if , then – admits an algorithm polynomial in the order of the input graph,
- if , then – is NP-complete.
To be continued.