-2
$\begingroup$

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.

$\endgroup$

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.

0
$\begingroup$

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.

$\endgroup$

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