Adott egy G=(S,T;E) páros gráf S={s1,...,sn}, T={t1,...,tk} csúcsosztályokkal, egy súlyfüggvény az éleken és egy d pozitív egész. A distance matching feladatban olyan legsúlyosabb M élrészhalmazt keresünk, amelyre a) minden S-beli csúcs foka legfeljebb egy és b) ha sit, sjt benne van M-ben, akkor |j-i| ≥ d.
A kérdés egy alkalmazását kapjuk, amennyiben S csúcsait egymást követő egész napos eseményeknek, T csúcsait biztonsági őröknek feleltetjük meg. Egy s nap és egy t őr között él megy, ha t beosztható az s napra. A feladat minél több naphoz hozzárendelni egy-egy őrt, ügyelve arra, hogy valamennyi őr minden egymást követő d napon legfeljebb egyszer dolgozhat (másképp: minden munkanap után d-1 pihenőnapot kell tartani). A súlyozott esetben az st él súlya az s esemény biztonságát jelöli a t őr felügyelete mellett, és legnagyobb összbiztonságú beosztást keresünk.
Többek között ismertek nehézségi és inapproximálhatósági eredmények, egy hatékony algoritmus nem túl nagy d esetére, és approximációs algoritmusok [1,2].
A feladat kapcsán sok nyitott kérdés van, és több vizsgálható rokon feladat is természetesen adódik. A hallgató feladata az eddigi eredmények feldolgozása, és a kérdéskör további vizsgálata.