Problème de couverture de chemin minimum

Nous travaillons dans des ordinateurs distribués et nous avons rencontré un problème de complexité qui se réduit à un problème de couverture de chemin minimum. Nous ne savons actuellement pas comment le résoudre. Le problème est le suivant:

Soit un entier, et soit un graphe contenant sommets. Nous étiquetons chaque sommet avec un couple tel que . Ci-après, nous nommons les sommets en utilisant leur étiquette. L'ensemble des arêtes dans est défini comme suit: . $k$ $Z_k$ $\frac{k(k+1)}{2}$ $(i,j)$ $1 \leq i \leq j \leq k$ $Z_k$ $\{ ((i,j),(i',j')) | i' >i \land j' \geq i \}$

Quelle est la couverture minimale du chemin de ? $Z_k$

La lecture de "On Path Cover Problems in Digraphs and Applications to Program Testing" par Ntafos et al. , nous avons vu que le chemin minimal couvrant est égal au cardinal du plus grand ensemble de sommets incomparables. Nous pensions à l'ensemble suivant: qui a un cardinal de . $S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$ $\frac{k^2}{4}-\frac{k}{2}$

Cordialement,

Pierre

graph-theory co.combinatorics application-of-theory Pierre
la source

doit-il être

au lieu de

dans la définition d'une arête de

j^{'} \geq j

$j' \ge j$

j^{'} \geq i

$j' \ge i$

Z_{k}

$Z_k$

Suresh Venkat

Réponses:

Il semble que votre graphique soit un DAG fermé de manière transitoire, non? Si c'est le cas (et c'est probablement une reformulation de ce que vous dites dans votre citation de Ntafos et al), le nombre minimum de chemins nécessaires pour couvrir le DAG est juste le nombre maximum d'éléments incomparables par paire; c'est le théorème de Dilworth .

Votre exemple peut être assez simple pour identifier directement cet ensemble incomparable maximum, mais en général il est possible de trouver cet ensemble en temps polynomial, par un algorithme basé sur la correspondance de graphes. La section "Preuve via le théorème de König" de l'article Wikipedia sur le théorème de Dilworth explique comment.

David Eppstein
la source