Pair formation: Find max number of disjoint pairs with distance less than $K$

Question

Here is an instance of the problem I am trying to solve:

In this graph there are two types of nodes:

1. $S$ stands for "start" nodes. You can think at them as the current locations of some postmen.
2. $E$ stands for "end" nodes. You can think at them as houses where a letter has to be delivered (people waiting for a letter to be delivered).

So basically there are some postmen that need to deliver letters to some locations (there can be any number of $E$ and $S$ edges, and the number of $E$ nodes does not necessarily match the number of $S$ nodes). Edge labels represent the known distance between two nodes.

Each postman cannot travel more than $K$. Each postman can deliver at most 1 letter. And each person $E$ is waiting exactly for 1 letter.

I need to find how many letters I can deliver. More formally, I am trying to find how many disjoint pairs $(s, e)$ with distance less than $K$ are there in my graph. In the example:

1. if $K=6$ then 3 letters can be delivered ($(s1, e1)$, $(s2, e3)$, $(s3, e4)$)
2. if $K=4$ then 2 letters can be delivered ($(s1, e2)$, $(s3, e3)$)

Note that the form of the graph is always like the one in the example, i.e. the nodes are "sorted" and form a "line".

Clearly, I have already tried with some brute force algorithm, but the graph I am dealing with can be very large and the complexity of such approach is not acceptable in my case. Do you have any idea? How can I efficiently find how many letters can be delivered?

Answer 1

Maximising the number of letters delivered can be done in polynomial time:

1. For each postman determine the houses they can reach. Since the graph is a line, this can be easily done by walking both ways, up to a distance of $K$, and noting which houses were encountered.
2. Make a bipartite graph where the vertices on each side represent postmen and houses respectivelty. Edges represent the ability of a particular postman to reach a particular house.
3. Find the maximum-cardinality matching in this bipartite graph (this can be done in several ways, e.g. Hopcroft–Karp). The result is an optimal allocation of postmen to houses, in terms of the number of letters delivered.

The above algorithm can be generalised to arbitrary graphs, whereupon the linear scan in step 1 becomes an all-pairs shortest path determination.