Recherche de chemins min-max sommet-disjoints avec une source commune sur les graphes planaires

Étant donné un graphe planaire non pondéré et une collection de paires de sommets ( est une constante), trouver chemins vertex-disjoints (sauf source) de à tel que la longueur du chemin le plus long soit minimisée. $(s,t_1),\dots,(s,t_k)$ $k\ge2$ $k$ $s$ $t_i$

Question: Existe - t-il un algorithme polynomial pour le problème?

Quelques résultats liés:

si n'est pas fixé, le problème est NP-difficile même si ; $k$ $t_1=\dots=t_k$
si le graphe d'entrée est pondéré et que les sources de chemins ne coïncident pas, c'est-à-dire que les chemins sont le problème est NP-difficile même pour ; $(s_1,t_1),\dots,(s_k,t_k)$ $k=2$
un problème avec un objectif différent, à savoir la minimisation de la somme des longueurs de trajet, est
- résoluble avec l'algorithme de flux de coût minimum pour les sources coïncidentes;
- NP-difficile pour les sources non coïncidentes et général ; $k$
- ouvert pour les sources non coïncidentes et constante . $k$

ds.algorithms graph-algorithms Sergey Pupyrev
la source

Il semble qu'il existe de nombreux résultats connexes. Pouvez-vous résumer les résultats importants liés à la question?

Tsuyoshi Ito du

Le graphe d'entrée G est-il pondéré (c'est-à-dire que chaque bord a une longueur entière positive)? J'avais supposé que G n'était pas pondéré, mais je me suis rendu compte que vous mélangez probablement les deux paramètres: (1) Si G est pondéré, le cas de k = 2 est NP-complet essentiellement par le théorème 14 dans le document de Kobayashi et Sommer auxquels vous avez lié, qui est également essentiellement le même que le dernier paragraphe de la section 2 de [HP02] cité dans ma réponse. (2) Si G n'est pas pondéré, je ne vois pas pourquoi le papier de Kobayashi et Sommer implique la dureté NP dans le cas de k = 2 et de sources différentes.

Tsuyoshi Ito

Dans mes paramètres, un graphique n'est pas pondéré, vous avez donc raison: mon affirmation sur la dureté NP en cas de K = 2 et de sources différentes est (probablement) fausse.

Sergey Pupyrev

J'ai mis à jour l'énoncé du problème en tenant compte du commentaire de Tsuyoshi Ito.

Sergey Pupyrev

Réponses:

Ce n'est pas exactement ce que vous avez demandé, mais le problème est NP-complet si k n'est pas une constante mais une partie de l'entrée.

Cela découle de la preuve du théorème 1 dans van der Holst et de Pina [HP02], qui dit: étant donné un graphe planaire G , des sommets distincts s et t dans G et des entiers positifs k et b , il est NP-complet de décider s'il existe k paires de vertex disjointes par paire entre s et t chacune de longueur au plus b .

Notez que le problème dans l'énoncé du théorème 1 est différent du vôtre à deux égards. Une différence est, comme je l'ai mentionné, que k est donné dans le cadre de l'entrée. L'autre est que le problème dans [HP02] concerne les chemins avec des points de terminaison communs au lieu des chemins avec une source commune et des récepteurs différents. Je ne sais pas comment corriger la première différence; la différence est si grande qu'il est probable que nous aurons besoin d'une preuve complètement différente pour fixer k . Mais je sais au moins comment corriger la deuxième différence.

La preuve du théorème 1 dans [HP02] donne une réduction de 3SAT. Cette réduction a la propriété suivante: dans l'instance ( G , s , t , k , b ) construite par la réduction, le degré de sommet t est toujours égal à k . Soit t ₁ ,…, t _k les k voisins de t . Ensuite, au lieu de demander s'il existe k chemins par paire en sommet-disjoint interne entre s et t chacun de longueur au plus bNous pouvons également demander s'il y a des chemins sommet-disjoints, sauf source par paires P ₁ , ..., P _k de telle sorte que chaque P _i est un chemin entre s et t _i de longueur au plus b -1.

[HP02] H. van der Holst et JC de Pina. Chemins disjoints limités en longueur dans les graphes plans. Discrete Applied Mathematics , 120 (1–3): 251–261, août 2002. http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3

Tsuyoshi Ito
la source

k

$k$

k

$k$

@SergeyPupyrev: Vous avez écrit que k est une constante. (Vous l'avez écrit parce que vous saviez ce que cela signifie, n'est-ce pas?) D'après ce que j'ai appris d'un examen rapide des articles pertinents, le fait que k soit une constante ou non dans des problèmes connexes semble faire une énorme différence dans l'état actuel de la complexité du problème.

Tsuyoshi Ito

k

$k$

k

$k$

@SergeyPupyrev: Je ne trouve pas de papier qui indique la complexité dans le cas où k est une constante, mais cela signifie seulement qu'elle m'est inconnue .

Tsuyoshi Ito