4
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – You Jie Aug 9 '18 at 7:39
  • $\begingroup$ 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... $\endgroup$ – Neal Young Aug 11 '18 at 12:58
  • $\begingroup$ @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. $\endgroup$ – Manuel Lafond Aug 13 '18 at 15:48
  • $\begingroup$ @ManuelLafond, good point, my suggestion doesn't work because each variable gadget cannot attach to multiple wires! Hmm. $\endgroup$ – Neal Young Aug 14 '18 at 0:12

Your Answer

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

Browse other questions tagged or ask your own question.