Skew-supermodular colouring with two 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 [math]m_1,m_2,n_1,n_2[/math] be positive integers such that [math]m_1 n_1+m_2 n_2=|S|[/math]. Can we decide in polynomial time if there is a partition [math]{\mathcal P}[/math] of S with [math]m_1[/math] classes of size [math]n_1[/math] and [math]m_2[/math] classes of size [math]n_2[/math], such that [math]|\{Y \in {\mathcal P}: Y \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}[/math] for every [math]X \subseteq S[/math]?


The problem is open even in the special case if the two functions [math]p_1[/math] and [math]p_2[/math] are intersecting supermodular. If [math]|n_1-n_2| \leq 1[/math], then the partition always exists (and can be found in polynomial time) by the skew-supermodular variant[1] of Schrijver's Supermodular colouring theorem. Another known special case is the result of Folkman and Fulkerson [2] that characterizes bipartite graphs that can be partitioned into [math]m_1[/math] matchings of size [math]n_1[/math] and [math]m_2[/math] matchings of size [math]n_2[/math]. For three distinct class sizes, the problem becomes NP-complete [3], see Skew-supermodular colouring with prescribed class-sizes.


  1. 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.
  2. J. Folkman, D.R. Fulkerson, Edge colorings in bipartite graphs, Combinatorial mathematics and its applications, University of North Carolina Press, Chapel Hill (1969).
  3. D. Pálvölgyi, Partitioning to three matchings of given size is NP-complete for bipartite graphs, EGRES Quick Proof no. 2013-01