<p>Your solution is always a correct 3HS, but does not guarantee a minimal subset U' e.g. a flow that goes through |S| many nodes from U with flow 1.</p>

<p>Btw I am sure the question was to find a 3-approximation in polynomial time.</p>

CC BY-SA 3.0
2017-02-19T22:13:51.790Z
2017-02-19T22:13:51.790Z
Kartoffel
<p>so i'm currently learning for an exam and got in an exercise the following question (a loose translation):</p>

<p>Find an Algorithm that finds the smallest U' ⊆ U that is a solution the 3 HITTING SET problem for a given U = {1..n} and S = {S1..Sk} with |Si| ≤ 3 so that U' ⋂ Si ≠ ∅ for every i.</p>

<p>Now my idea was to build an s-t-network over a bipartite graph with a set of Nodes U' wich contains a node for each element of U, and a set of nodes S' with a node for each element of S. The edges and their capacity are, c(s, u) = infinite for each u ∈ U', c(u, v) = 1 for each v ∈ S' and the to u corresponding element of U is also element of the to v corresponding set Si, and finally c(v, t) = 1.</p>

<p>Now I would just use a variant of the ford fulkerson algorithm which to select a path using only u nodes which already has been used, and only if no such path exists, it searches for any path.
If the algorithm terminates with a flow of |S| the set {u | u ∈ U' with f(s, u) > 0} is the solution.</p>

<p>But because 3HS (which can easily be reduced from a hyper vertex cover problem) is NP-complete, and max flow is not this can't be a valid solution.</p>

<p>So my question is, what did i do wrong.</p>

<ds.algorithms><np-complete><max-flow><bipartite-graphs>
3-Hitting-Set - maximum flow algorithm
Frederic K.
# 3-Hitting-Set - maximum flow algorithm

(Asked by: username_0 on 2017-02-19)

so i'm currently learning for an exam and got in an exercise the following question (a loose translation):

Find an Algorithm that finds the smallest U' ⊆ U that is a solution the 3 HITTING SET problem for a given U = {1..n} and S = {S1..Sk} with |Si| ≤ 3 so that U' ⋂ Si ≠ ∅ for every i.

Now my idea was to build an s-t-network over a bipartite graph with a set of Nodes U' wich contains a node for each element of U, and a set of nodes S' with a node for each element of S. The edges and their capacity are, c(s, u) = infinite for each u ∈ U', c(u, v) = 1 for each v ∈ S' and the to u corresponding element of U is also element of the to v corresponding set Si, and finally c(v, t) = 1.

Now I would just use a variant of the ford fulkerson algorithm which to select a path using only u nodes which already has been used, and only if no such path exists, it searches for any path.
If the algorithm terminates with a flow of |S| the set {u | u ∈ U' with f(s, u) > 0} is the solution.

But because 3HS (which can easily be reduced from a hyper vertex cover problem) is NP-complete, and max flow is not this can't be a valid solution.

So my question is, what did i do wrong.

**Tags:** ds.algorithms, np-complete, max-flow, bipartite-graphs

---

## 1 answers

### Answer by username_1 on 2017-02-19. Score: 0 | Accepted answer

Your solution is always a correct 3HS, but does not guarantee a minimal subset U' e.g. a flow that goes through |S| many nodes from U with flow 1.

Btw I am sure the question was to find a 3-approximation in polynomial time.


---

