5
$\begingroup$

I have been looking in general for results on matching for regular hypergraphs that are not uniform, but I could not find any. Papers I found by internet search seem to focus on uniform hypergraphs (sometimes in addition to being regular). The relative scarcity of results on regular hypergraph matching is somewhat puzzling, since uniform and regular hypergraphs are duals of each other and one would expect that matching may have been studied for both kinds.

I would appreciate if someone can point me to any sources. Of most interest to me are necessary and/or sufficient conditions for existence perfect matchings and closed form expressions or bounds for fractional matchings. I am also curious to know explanations (conceptual, historical etc) for the lack of results of this kind for regular hypergraphs.

Edit: A matching is a collection of pairwise disjoint hyperedges; a perfect matching is a matching that covers all vertices.

$\endgroup$
  • 2
    $\begingroup$ How do you define a perfect matching in a hypergraph? $\endgroup$ – Tyson Williams May 20 '12 at 13:47
  • $\begingroup$ @TysonWilliams added a definition above. $\endgroup$ – Ankur May 20 '12 at 19:27
  • 1
    $\begingroup$ As you have observed, the dual of a regular hypergraph is uniform. A matching of a regular hypergraph corresponds to a strong independent set in its dual. You would try to search with "strong independent set" in a "uniform hypergraph." $\endgroup$ – Yoshio Okamoto May 30 '12 at 9:37
5
$\begingroup$

You are asking many things in the question, and I can only answer part of it:

necessary and/or sufficient conditions for existence perfect matchings

It is unlikely that a nice necessary and sufficient characterization is known, because deciding whether a given 3-regular hypergraph has a perfect matching or not is NP-complete. Indeed, it is equivalent to the monotone 1-in-3 SAT problem, which is proved to be NP-complete by Schaefer [Sch78]. (In [Sch78], the same problem is called “ONE-IN-THREE SATISFIABILITY” without the word “monotone.”) To see this equivalence, interpret each hyperedge as a variable and each vertex as a clause.

[Sch78] Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pp. 216–226, May 1978. DOI: 10.1145/800133.804350.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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