2
$\begingroup$

Similar with Weighted matching algorithm for minimizing max weight. Consider the following matching problem:

Input: a complete weighted bipartite graph with $n+(k*n)$ vertices, given by $n$, $k*n$, and $w_{ij}$ a weight matrix for each edge connecting $i \in [n]$ and $j \in [k*n]$.

Output: a perfect "1-to-k" matching 𝑀:$[𝑛]↣[k*n]^k$ where each vertices on the left side is equally connected to $k$ vertices on the right side, minimizing the following function:

$max_i\Sigma_{j\in M(i)}w_{ij}$.

Is this NP-hard problem or a polynomial way to solve it?

$\endgroup$
4
  • 1
    $\begingroup$ (i) I assume you intend that each vertex on the right should be matched to just one vertex on the left. (ii) Per the posting guidelines, can you explain where the problem arises for you, and what you've tried? (iii) Seems to me like it's in P by an easy reduction to matching. $\endgroup$
    – Neal Young
    Apr 13 at 15:03
  • $\begingroup$ @NealYoung (i) Yes, every vertex on the right should be matched to only one vertex on the left. (ii) I'm building a distributed cache system with a cache on each worker, and the input data is batches of sets of elements (e.g., a batch of token sequence), I want to evenly allocate these samples to the most proper worker to maximize the cache hit and minimize extra communication overhead. $\endgroup$
    – Han Tian
    Apr 14 at 3:59
  • $\begingroup$ I spoke too soon... the problem is NP-hard (even for fixed $n\ge 2$, or fixed $k\ge 3$). The restrictions to $k=1$ or $n=1$ are in P. I'm not sure about the restriction to $k=2$. $\endgroup$
    – Neal Young
    Apr 14 at 16:33
  • $\begingroup$ Closely related: cstheory.stackexchange.com/questions/54185/… ? $\endgroup$
    – Neal Young
    Apr 14 at 16:40

1 Answer 1

1
$\begingroup$

The problem is hard if $k$ is part of the input (not fixed):

Lemma 1. The problem is NP-hard, even for $n=2$.

The problem is also hard if $k$ (but not $n$) is fixed (with $k\ge 3$):

Lemma 2. The problem is strongly NP-hard, even for $k=3$.

The problem is in P if $k=1$ or $n=1$:

Lemma 3. The problem is in P for $k=1$ or $n=1$.

We leave open whether the problem is NP-hard for $k=2$.


Proof of Lemma 1. The proof is by reduction from the NP-hard Two-Way Balanced Partition problem. Fix an instance $x \in \mathbb N^{2n'}$ of Two-Way Balanced Partition. The goal is to determine whether there is a subset $S\subseteq [2n']$ of size $n'$ such that $\sum_{j\in S} x_j = \lambda$, where $\lambda = \sum_{j=1}^{2n'} x_j / 2$. Given $x$, the reduction outputs the instance $(n, k, w, \lambda)$ of the decision version of OP's problem $n=2$, $k=n'$, and $w_{ij} = x_j$ for $(i, j) \in [2]\times [2n']$.

Next we verify that the reduction is correct. Suppose that there is a feasible subset $S$ for $x$, so $\sum_{j\in S} x_j = \lambda$. Then the 1-to-$k$ matching $M$ defined by $M(1) = S$ and $M(2) = [2n']\setminus S$ has cost $\lambda$. Conversely, suppose that there is a 1-to-$k$ matching $M$ of cost at most $\lambda$. Then taking $S=M(1)$ gives a feasible subset for $x$. $~~~\Box$


Proof of Lemma 2. The proof is by reduction from the strongly NP-hard 3-Partition problem. Fix an instance $x \in \mathbb N^{3n}$ of 3-Partition. The goal is to determine whether there is a partition $C$ of $[3n]$ into $n$ triples such that $\sum_{j\in C_i} x_j$ equals $\lambda$ for each triple $C_i$ in $C$, where $\lambda = \sum_{j=1}^{3n} x_j/n$.

Given $x$, the reduction outputs the instance $(n, k, w, \lambda)$ of the decision version of OP's problem where $k=3$, and $w_{ij} = x_j$ for $(i, j) \in [n]\times [3n]$.

Next we verify that the reduction is correct. Suppose that there is a feasible partition $C$ for $x$, so $\sum_{j\in C_i} x_j = \lambda$ for each triple $C_i$ in $C$. Then the 1-to-3 matching $M$ defined by $M(i) = C_i$ for each $i\in [n]$ has cost $\lambda$.

Conversely, suppose that there is a 1-to-3 matching $M$ of cost at most $\lambda$. Then taking $C_i=M(i)$ for $i\in [n]$ gives a feasible partition $C$ for $x$. $~~~\Box$


Proof of Lemma 3. For any instance with $n=1$, there is only one possible solution $M(1) = [k]$, so the optimum can be found in linear time.

Given an instance $(k=1, n, w, \lambda)$ of the decision variant of OP's problem, the instance can be solved by reduction to the bipartite matching instance $G=(U, W, E)$ where $U = W = [n]$ and $E = \{(i, j) : w_{ij} \le \lambda\}$, which has a perfect matching iff OP's instance has a 1-to-1 matching of cost at most $\lambda$.

The optimization version of OP's problem can be solved using $O(\log n)$ iterations of binary search, over $\lambda$ in $\{w_{ij} : (i, j) \in [n] \times [n]\}$, to find the minimum $\lambda$ such that there is a solution of cost at most $\lambda$.

EDIT: The case $k=1$ was asked about here. (Answers pointed out that it is studied under the name Bottleneck Matching.) $~~~~\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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