Skew-supermodular colouring with prescribed class-sizes

From Egres Open
Jump to: navigation, search

Let [math]p_1[/math] and [math]p_2[/math] be integer skew-supermodular set functions on ground set S such that [math]\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}[/math] for every [math]X \subseteq S[/math], and let us be given k nonnegative integers [math]n_1,n_2,\dots,n_k[/math]. Decide whether there is a good colouring of [math]S[/math] with these class sizes, that is a partition [math]\{Y_1,\dots,Y_k\}[/math] of S such that [math]|\{i: Y_i \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}[/math] for every [math]X \subseteq S[/math], and [math]|Y_i| = n_i[/math] for every i=1,...,k?

Solved b.jpg

It was shown by R.R. Kamalian and V.V. Mkrtchyan [1], and independently by Dömötör Pálvölgyi [2], that the following special case is already NP-complete: Given a subcubic bipartite graph [math]G=(V,E)[/math] and two positive integers [math]a,b[/math], decide if [math]E[/math] can be partitioned into a perfect matching, a matching of size [math]a[/math], and a matching of size [math]b[/math].


If the class sizes are almost equal (that is [math]|n_i-n_j|\le 1[/math] for every [math]1\le i\ltj\le k[/math]) then the answer to the above question is always YES by the skew-supermodular variant[3] of Schrijver's Supermodular colouring theorem.

A special case of this problem is the following: given a bipartite graph G=(A,B,E) with [math] d_G(v)\le k[/math] for every [math]v\in A\cup B[/math], and k positive integers [math]n_1,n_2,\dots,n_k[/math] satisfying [math]n_1+n_2+\dots+n_k = |E|[/math]. Does there exist k disjoint matchings [math]M_1,M_2,\dots,M_k\subseteq E[/math] such that [math]|M_i| = n_i[/math] for every i=1,...,k? This is also NP-complete by [2], but if the list [math]n_1,n_2,\dots,n_k[/math] contains at most two distinct positive integers, then there is a characterization and an algorithm by a result of Folkman and Fulkerson [4]. A generalization of this for supermodular colouring is posed as an open question: Skew-supermodular colouring with two class sizes.


  1. R.R. Kamalian, V.V. Mkrtchyan, On complexity of special maximum matchings constructing, DOI link, arXiv link
  2. 2.0 2.1 D. Pálvölgyi, Partitioning to three matchings of given size is NP-complete for bipartite graphs, EGRES Quick Proof no. 2013-01
  3. A. Bernáth, T. Király, Covering skew-supermodular functions by hypergraphs of minimum total size, Operations Research Letters 37 (2009), 345-350. DOI link, EGRES Technical Report.
  4. J. Folkman, D.R. Fulkerson, Edge colorings in bipartite graphs, Combinatorial mathematics and its applications, University of North Carolina Press, Chapel Hill (1969).