Transversal partitioning in balanced hypergraphs (Q1372732)

The problem of partitioning transversals of a hypergraph into pairwise disjoint transversals is studied. A \(k\)-fold transversal of a hypergraph is a set of vertices that contains at least \(k\) elements of every hyperedge. The main result is that in a balanced hypergraph for every \(k\leq\gamma\), where \(\gamma\) is the minimum cardinality of a hyperedge, each \(k\)-fold transversal can be partitioned in polynomial time into \(k\) pairwise disjoint 1-fold transversals. For totally balanced hypergraphs also an NC algorithm is given. As a corollary it is deduced e.g. that the dominating partition problem, i.e. to find a partition of the vertex set of a graph into a maximal number of dominating sets, is in NC for strongly chordal graphs, whereas for general chordal graphs this problem is known to be NP-complete.