Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have two 2D arrays: $P[n][s]$ and $C[n][s]$, $s \leq n$.
P contains sets of nodes and $C$ the cost of a set in $P$, e.g. the cost of $P[2][2]$ is $C[2][2]$ and a set $p \in P = \{ s_0, s_1, ..., s_{n-1} \}^q, q \leq n$, e.g. $p=\{s_0, s_3\}$.
For every row I can pick at most one set but in the end the union of the picked sets needs to contain all nodes $\{s_0, s_1, ..., s_{n-1} \}$.
How do I find the least expensive picks in linear time?
If you are able to find the least expensive picks in linear (or even polynomial) time then $P=NP$.
Your problem is a generalization of the set-cover problem: given a set $X$ of items and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^X$ of subsets of $X$, find $S' \subseteq S$ such that $\cup_{S_i \in S'} S_i = X$ and $|S'|$ is minimized.
This is exactly your problem once you set $n=|X|$, $s=1$, $P[i][1] = S_i$, and $C[i][1]=1$.
