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 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.


This entry was posted in compressing and summarizing, digraph theory, Mathematics, News, Research. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s