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.


closed as off-topic by Jan Johannsen, Yuval Filmus, András Salamon, Kaveh, David Eppstein Feb 21 '17 at 3:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Jan Johannsen, Yuval Filmus, András Salamon, Kaveh, David Eppstein
If this question can be reworded to fit the rules in the help center, please edit the question.


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.


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