-hard and linear variants of hypergraph partitioning

This article presents an infinite family of combinatorial problems that shows abrupt changes of complexity between neighbour problems. We define problem as a purely constraint-driven variant of hypergraph partitioning with parameters k and l as follows. Given a hypergraph on n vertices and k sizes of colours t1,…,tk of sum n, can we colour the vertices with k colours of given size such that each hyperedge intersects at most l colours? We show that, for fixed parameters k and l, is: polynomial when l=1, and -complete when l≠1 on the class of hypergraphs; -complete when l=1, and linear when l≠1 on the class of hypergraphs with pairwise disjoint hyperedges. This inversion of complexity is possible since hypergraphs with disjoint hyperedges can be encoded in a more compact way, namely Θ(mlog(n)) instead of Θ(mn) bits (n and m are the number of vertices and edges of the hypergraph).