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.


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.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.