<p>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.</p>

<p>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.</p>

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

CC BY-SA 4.0
2018-08-09T07:39:10.497Z
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
CC BY-SA 4.0
2018-08-11T12:58:10.800Z
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
CC BY-SA 4.0
2018-08-13T15:48:34.933Z
@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
CC BY-SA 4.0
2018-08-14T00:12:08.030Z
@ManuelLafond, good point, my suggestion doesn't work because each variable gadget cannot attach to multiple wires!  Hmm.
Neal Young
<cc.complexity-theory><graph-theory><np-hardness>
A variant of hitting set: finding a matching to hit all edge sets
You Jie
# A variant of hitting set: finding a matching to hit all edge sets

(Asked by: username_0 on 2018-08-04)

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

**Tags:** cc.complexity-theory, graph-theory, np-hardness

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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...  
> **username_2**: @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.  
> **username_1**: @ManuelLafond, good point, my suggestion doesn't work because each variable gadget cannot attach to multiple wires!  Hmm.  

---

## 0 answers

