In general, the hitting set problem is given a family $\cal S$ of sub-sets, $\{S_1, \cdots, S_h\}$, and a universal set $U = \bigcup_{i\in [1,h]} S_i$. It asks for a minimum set $H \subseteq U$ hitting all sub-sets of $\cal S$, and as we know, it is NP-hard. Now the problem is defined as following.

Let $K$ be a clique, and $\{K_1, \cdots, K_h\}$ be a collection of sub-cliques of $K$. A matching is a set of pairwise disjoint edges. The question now is to find a matching $M$ of $K$ that hits every $E(K_i)$ for $i \in [1,h]$, where $E(K_i)$ is the edge-set of $K_i$, and $M$ hits every $E(K_i)$ if for any $E(K_i)$ (with $i \in [1,h]$), there is an edge $uv\in M$ that is an edge of $E(K_i)$ as well.

For now, I can show that if what we want is a minimum matching, then the problem is NP-hard. So is it still hard to find a minimal matching hitting every $E(K_i)$?

  • Thanks for your comments, and sorry about the ambiguous expression. I had removed the first paragraph, since I think the second paragraph is enough to express the problem. In the second paragraph, I refined the expression of the problem. Precisely, a matching $M$ hits all $E(K_i)$ (previous I used $S_i$), if for every $E(K_i)$, there is an edge $uv \in M$ that is an edge of $E(K_i)$ as well. – You Jie Aug 9 at 7:39
  • The problem is clear now. I think you can show NP-hardness by a reduction from one-in-three SAT to the special case of your problem when each clique $K_i$ is a triangle. For each variable introduce a gadget consisting of the union of three triangles, with (resp.) vertex sets $\{a, b, d\}, \{b, d, e\}, \{b, e, c\}$, with two possible solutions $\{(a,d), (b,e)\}$ and $\{(b, d), (c, e)\}$. For each clause introduce one new triangle, and connect each edge of the clause gadget (corresponding to a literal) to its variable gadget with a "wire" (w/ 1 new vertex) similar to the variable gadget... – Neal Young Aug 11 at 12:58
  • @NealYoung Would you be interested in expanding your comment into an answer? This seems like a nice idea, but I'm trying to see what happens when a single variable is 'used' to satisfy multiple clauses. – Manuel Lafond Aug 13 at 15:48
  • @ManuelLafond, good point, my suggestion doesn't work because each variable gadget cannot attach to multiple wires! Hmm. – Neal Young 2 days ago

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.