1
$\begingroup$

I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers that MO users may provide.

It is well known that for $k\geq 3$ finding the matching number of a $k$-uniform $k$-partite hypergraph is NP hard in general. Are there subclasses of these hypergraphs for which the problem is solvable in polynomial time?

$\endgroup$
2
  • $\begingroup$ Just to clarify: By matching number, do you mean the number of perfect matchings in the hypergraph? Or whether the hypergraph has a matching or not? $\endgroup$
    – Zur Luria
    Apr 5, 2012 at 13:22
  • $\begingroup$ By matching number I mean finding the largest number of pairwise disjoint hyperedges. $\endgroup$
    – Ankur
    Apr 18, 2012 at 22:25

1 Answer 1

1
$\begingroup$

I'm assuming that by matching number, you mean the maximum number of pairwise disjoint edges. There are a few viewpoints you might want to try. One is that the maximum matching is the same as the maximum independent set of the dual hypergraph. (Hypergraphs have weak independent sets where no edge is completely contained, and strong independent sets where you pick no two points from any edge; here I mean strong.) Moreover, the independent sets of a hypergraph are the same as the independent sets of the 1-skeleton (where every hyperedge is replaced by a clique). So possibly, there are classes of graphs for which independent set is polynomial-time solvable, which have an interpretation as coming from 3-partite 3-uniform hypergraphs. Bounded treewidth is one concrete example to try.

One class of hypergraphs where matching is in P, is for interval hypergraphs. But, the class of 3-partite 3-uniform interval hypergraphs is very limited. Here's one more general class that is poly-time solvable: the set of 3-partite 3-uniform hypergraphs where each of the 3 vertex parts have labels ${1, 2, ..., n/3},$ and where for every edge the labels of its three vertices are within a constant distance of each other. You can show using dynamic programming that the matching problem is solvable here in polynomial time. On the other hand, that's not really making essential use of the 3-partite or 3-uniformness.

If you're looking for leads I would suggest "Hypergraphs," Part VIII of Schrijver's Combinatorial Optimization book. It discusses what properties of hypergraphs are sufficient to give poly-time solutions to basic quantities such as the matching number.

$\endgroup$
2
  • $\begingroup$ Thanks so much and sorry for the late reply. The labelled hypergraph you describe may be useful to me. But I didn't quite understand how you are labeling the partitions of your hypergraph. Also, could you explain what you mean by the "distance" of the labels? Is there a source for this particular result and the DP argument? $\endgroup$
    – Ankur
    Apr 18, 2012 at 22:34
  • $\begingroup$ The family I had in mind is the following: number the vertices 1, 2, 3, 4, 5, ... (3-partiteness and 3-uniformity are not actually needed so I will drop that) and assume that for each two vertices i, j in a common hyperedge, |i-j| <= C for a fixed constant C. Then you can compute a max matching in exp(C)*poly(n) time. The dynamic program table has an entry [k, S] for every 1<=k<=n and subset S of k+1..k+C, meaning "what's the maximum matching in the induced subhypergraph on vertex set {1, 2, .., k} union S?" It's a lot like typical DP on bounded-treewidth graphs (and generalizes to trees too). $\endgroup$ Apr 29, 2012 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.