<p>Regarding the NP-hardness tag, your problem can be shown to be in <span class="math-container">$P$</span> (and thus likely not <span class="math-container">$NP$</span>-hard) via a reduction to min-cost flow with <span class="math-container">$O(nK)$</span> vertices and <span class="math-container">$O(nK^2)$</span> edges.</p>

<p>It will help to have a visual to refer to for the construction. Below is a figure showing how we construct the min-cost flow instance with <span class="math-container">$n=K=3$</span>, with the set family <span class="math-container">$A=\{1,2\}, B=\{1,2,3\}, C=\{2,3\}$</span>.</p>

<p><a href="https://i.sstatic.net/11qjM.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/11qjM.png" alt="Construction"></a></p>

<p>All edges are directed rightwards. Red edges have cost 0 and capacity 1. Blue edges have cost 0 and capacity <span class="math-container">$K$</span>. Black edges have capacity <span class="math-container">$1$</span> and cost indicated in the figure. We demand that <span class="math-container">$s$</span> route <span class="math-container">$K=3$</span> units of flow to <span class="math-container">$t$</span>.</p>

<p>We refer to the nodes corresponding to <span class="math-container">$[n]$</span> (above labeled <span class="math-container">$1$</span>, <span class="math-container">$2$</span>, and <span class="math-container">$3$</span>) as "number nodes" and those corresponding to the <span class="math-container">$K$</span> sets (above labeled <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$C$</span>) as "set nodes". The unlabeled nodes are called "central nodes", and we say that a given central node <em>corresponds</em> to the unique adjacent number node.</p>

<p>All costs and capacities are integral, so w.l.o.g. we can consider only integral feasible solutions to the problem. The capacity constraints on the red edges ensure that, in any feasible solution, each set node must send over exactly one unit of flow to <span class="math-container">$t$</span>, corresponding to the constraint that we pick one element from each set. This unit of flow must have arrived from one of the <span class="math-container">$nK$</span> central nodes, which in turn must have arrived from its corresponding number node. Finally, this number node received its flow from <span class="math-container">$s$</span>.</p>

<p>Thus, if we track the path taken by each unit of flow in a solution to the constructed flow instance, we see that it goes through both a number node <span class="math-container">$c$</span> and through a set node <span class="math-container">$S$</span>, corresponding to a choice of a number <span class="math-container">$c$</span> from that set <span class="math-container">$S$</span> in the original instance. As for the costs, any solution that routes <span class="math-container">$p_i$</span> units of flow to a number node labeled <span class="math-container">$i$</span> must incur a cost of at least <span class="math-container">$\sum_{j=1}^{p_i}\left(2j-1\right) = {p_i}^2$</span> on the node's out-edges. In an optimal solution, this holds with equality. As all other edges have zero cost, optimal solutions to this flow problem thus have cost <span class="math-container">$\sum_{i=1}^{n}{p_i}^2$</span>, as desired.</p>

<p>In general, <span class="math-container">$s$</span> has a blue edge to each of <span class="math-container">$n$</span> number nodes (labeled <span class="math-container">$1, 2, \cdots, n$</span>), each of which is adjacent to its own distinct set of <span class="math-container">$K$</span> different central nodes. The edges connecting the number nodes to the central nodes all have capacity <span class="math-container">$1$</span> and varying costs equal to the first <span class="math-container">$K$</span> positive odd numbers. A central node corresponding to a number node with label <span class="math-container">$c$</span> is then connected with a blue edge to each of the set nodes for which the set contains <span class="math-container">$c$</span>. The set nodes correspond to each of the <span class="math-container">$K$</span> sets. Finally, all set nodes are connected to <span class="math-container">$t$</span> with a red edge.</p>

<p>More generally, the same construction works with any convex cost structure, after the necessary modifications.</p>

CC BY-SA 4.0
2020-06-03T04:47:26.547Z
That's super clear and very interesting! Thank you :)
vervenumen
CC BY-SA 4.0
2020-06-03T04:50:57.553Z
A follow up question, if I had to choose x>1 numbers from each subset while minimizing the same sum of squares constraint would it be equally easy? If you feel so, I'll give it a try.
vervenumen
CC BY-SA 4.0
2020-06-03T09:49:33.890Z
If a number can be picked more than once for a single set, I believe the same construction should work after changing the capacity on red edges (or, equivalently, replicating each set node $x$ times). If each number can be picked at most once per set, I think it can still be solved with a similar idea, but requires an added layer between the central vertices and the set vertices to "bottleneck" the amount of flow that set $S$ gets from element $c$.
Yonatan N
CC BY-SA 4.0
2020-06-03T04:35:01.110Z
2020-06-04T05:40:08.257Z
2020-06-04T05:40:08.257Z
Yonatan N
<p>Problem is as follows:
We are given <span class="math-container">$K$</span> subsets of <span class="math-container">$\{1,2,...,n\}$</span>. We need to pick one number from each of these subsets such that <span class="math-container">$\sum_{i=1}^n p_i^2$</span> is minimized where <span class="math-container">$p_i$</span> is the number of times <span class="math-container">$i$</span> is repeated among picked numbers. Is there an efficient algorithm to do this?</p>

CC BY-SA 4.0
2020-06-03T02:12:13.917Z
Try casting this as a min-cost flow problem.
Yonatan N
<cc.complexity-theory><np-hardness><np-complete>
Choosing one number from each set so that the sum of squares of each distinct number counts is minimized
vervenumen
# Choosing one number from each set so that the sum of squares of each distinct number counts is minimized

(Asked by: username_0 on 2020-06-03)

Problem is as follows:
We are given $K$ subsets of $\{1,2,...,n\}$. We need to pick one number from each of these subsets such that $\sum\_{i=1}^n p\_i^2$ is minimized where $p\_i$ is the number of times $i$ is repeated among picked numbers. Is there an efficient algorithm to do this?

**Tags:** cc.complexity-theory, np-hardness, np-complete

> **Comments:**
> **username_1**: Try casting this as a min-cost flow problem.  

---

## 1 answers

### Answer by username_1 on 2020-06-03. Score: 5 | Accepted answer

Regarding the NP-hardness tag, your problem can be shown to be in $P$ (and thus likely not $NP$-hard) via a reduction to min-cost flow with $O(nK)$ vertices and $O(nK^2)$ edges.

It will help to have a visual to refer to for the construction. Below is a figure showing how we construct the min-cost flow instance with $n=K=3$, with the set family $A=\{1,2\}, B=\{1,2,3\}, C=\{2,3\}$.

[![Construction](https://i.sstatic.net/11qjM.png)](https://i.sstatic.net/11qjM.png)

All edges are directed rightwards. Red edges have cost 0 and capacity 1. Blue edges have cost 0 and capacity $K$. Black edges have capacity $1$ and cost indicated in the figure. We demand that $s$ route $K=3$ units of flow to $t$.

We refer to the nodes corresponding to $[n]$ (above labeled $1$, $2$, and $3$) as "number nodes" and those corresponding to the $K$ sets (above labeled $A$, $B$, and $C$) as "set nodes". The unlabeled nodes are called "central nodes", and we say that a given central node *corresponds* to the unique adjacent number node.

All costs and capacities are integral, so w.l.o.g. we can consider only integral feasible solutions to the problem. The capacity constraints on the red edges ensure that, in any feasible solution, each set node must send over exactly one unit of flow to $t$, corresponding to the constraint that we pick one element from each set. This unit of flow must have arrived from one of the $nK$ central nodes, which in turn must have arrived from its corresponding number node. Finally, this number node received its flow from $s$.

Thus, if we track the path taken by each unit of flow in a solution to the constructed flow instance, we see that it goes through both a number node $c$ and through a set node $S$, corresponding to a choice of a number $c$ from that set $S$ in the original instance. As for the costs, any solution that routes $p\_i$ units of flow to a number node labeled $i$ must incur a cost of at least $\sum\_{j=1}^{p\_i}\left(2j-1\right) = {p\_i}^2$ on the node's out-edges. In an optimal solution, this holds with equality. As all other edges have zero cost, optimal solutions to this flow problem thus have cost $\sum\_{i=1}^{n}{p\_i}^2$, as desired.

In general, $s$ has a blue edge to each of $n$ number nodes (labeled $1, 2, \cdots, n$), each of which is adjacent to its own distinct set of $K$ different central nodes. The edges connecting the number nodes to the central nodes all have capacity $1$ and varying costs equal to the first $K$ positive odd numbers. A central node corresponding to a number node with label $c$ is then connected with a blue edge to each of the set nodes for which the set contains $c$. The set nodes correspond to each of the $K$ sets. Finally, all set nodes are connected to $t$ with a red edge.

More generally, the same construction works with any convex cost structure, after the necessary modifications.

> **Comments:**
> **username_0**: That's super clear and very interesting! Thank you :)  
> **username_0**: A follow up question, if I had to choose x>1 numbers from each subset while minimizing the same sum of squares constraint would it be equally easy? If you feel so, I'll give it a try.  
> **username_1**: If a number can be picked more than once for a single set, I believe the same construction should work after changing the capacity on red edges (or, equivalently, replicating each set node $x$ times). If each number can be picked at most once per set, I think it can still be solved with a similar idea, but requires an added layer between the central vertices and the set vertices to "bottleneck" the amount of flow that set $S$ gets from element $c$.  

---

