3
$\begingroup$

I know that it is NP-hard to find out whether a $3$-graph (that is, a $3$-uniform hypergraph) has a perfect matching. Now the problem asks us to prove the same for any $k$-graph for any $k \ge 4$. The hint says to assume there's a polynomial time algorithm to decide this for a $k$-graph and then show that thus we can decide on a perfect matching for a $3$-graph in polynomial time.

For that I guess we have to build a $k$-graph (say a $4$-graph) from a $3$-graph so that we would have a perfect matching in the former iff we have a perfect matching in the latter. The first thought I had was to put one new vertex into each edge not affecting the intersections but in order to cover these extra vertices one would need all the edges in the matching which is impossible. What's a better way of doing it?

$\endgroup$
2
  • $\begingroup$ $k$-graph is a regular graph of degree $k$? $\endgroup$
    – kabenyuk
    Commented Dec 9, 2022 at 14:22
  • $\begingroup$ $k$-graph or a $k$-uniform hypergraph is where every edge contains $k$ vertices. $\endgroup$
    – kleinbottle
    Commented Dec 9, 2022 at 14:23

1 Answer 1

Reset to default
2
$\begingroup$

Suppose that the $3$-uniform hypergraph we start with has $n$ vertices, so that a perfect matching (if it has one) has $\frac n3$ edges. To turn this into a $4$-uniform hypergraph, add $\frac n3$ new vertices $v_1, v_2,\dots, v_{n/3}$, and replace each edge $e$ by $\frac n3$ edges of the form $e \cup \{v_i\}$ for $i=1, \dots, \frac n3$.

A similar construction works to create $k$-uniform hypergraphs for $k > 4$, except that of course more vertices need to be added. If we are careful, a $3$-uniform hypergraph with $n$ vertices and $m$ edges turns into a $k$-uniform hypergraph with $\frac{kn}{3}$ vertices and $\frac{mn}{3}$ edges.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .