La complexité de ce problème de chemin est-elle connue?

Instance: un graphe non orienté $G$ avec deux sommets distingués et un entier . $s\neq t$ $k\geq 0$

Question: Est -ce qu'il existe un chemin dans , de telle sorte que le chemin croise au plus triangles? (Pour ce problème, un chemin est censé couper un triangle si le chemin contient au moins une arête du triangle.) $s-t$ $G$ $k$

cc.complexity-theory graph-algorithms Andras Farago
la source

Est-ce mal? Nous attribuons du poids à chaque bord, puis nous trouvons le chemin le plus court. Le poids de chaque arête est le nombre de triangles qui incluent cette arête. Le poids de ce chemin n'est pas égal au nombre de triangles qu'il rencontre mais c'est un chemin st avec un nombre minimum de triangles. (Le problème possible est que nous pouvons compter un ou plusieurs triangles deux fois parce que nous visitons deux bords de ce triangle, mais la raison pour laquelle nous les choisissons est qu'ils sont plus petits que de passer par l'autre bord du triangle et que nous avons également des moyens de chemin simples deux bords d'un triangle sont côte à côte).

Saeed

@Saeed Je ne comprends pas: quel est l'argument selon lequel le comptage excessif ne vous fait pas choisir un chemin sous-optimal? Votre algorithme est certainement une approximation 2. Peut-être qu'une solution consiste à ajouter une arête

(u, w)

$(u, w)$ pour chaque chemin

u \to v \to w

$u\to v \to w$ avec un poids égal au nombre de triangles contenant à la fois

(u, v)

$(u,v)$ et

(v, w)

$(v,w)$

Sasho Nikolov

Bon, on peut passer de u à v puis on choisit x (un autre noeud pas dans le triangle uvw) puis on va vers w qui est faux (mon erreur était que j'ai raté entre des sommets qui ne sont pas dans le triangle uvw) , mais avec votre correction, c'est correct car pour chaque chemin st avec

triangles

dans le graphique d'origine, il y a un chemin de poids

dans le graphique auxiliaire. De plus, le poids du chemin dans le nouveau graphique est toujours au moins égal au nombre de triangles dans le chemin correspondant dans le graphique d'origine.

α

$\alpha$

α

$\alpha$

Saeed

J'y réfléchis un peu plus, même après correction, cela ne fonctionne pas. Désolé Andras si j'ai apporté un mauvais espoir. Pour voir pourquoi la correction est incorrecte, considérons les sommets

dans un chemin

et nous avons un triangle

et supposons que les arêtes

sont également incidentes de nombreux triangles. Si nous utilisons une nouvelle arête artificielle qui relie

alors nous comptons le triangle

u - > v - > w - > x

$u->v->w->x$

P

$P$

u, v, w

$u,v,w$

v, w, x

$v,w,x$

v x

$vx$

u w

$uw$

u - > w

$u->w$

deux fois. PS: Mon raisonnement était à nouveau faux parce que je pensais que nous remplacions simplement

par un nouveau bord (multi)

. Si nous ajoutons ces bords artificiels pour chaque chemin, cela fonctionnera trivialement. Il semble que ce soit un PNJ.

v, w, x

$v,w,x$

u - > v

$u->v$

v - > w

$v->w$

u - > w

$u->w$

Saeed

Mon idée ne fonctionnera pas - j'aurais besoin de maintenir plusieurs ensembles, et je pense qu'il y en aura trop.

reinierpost

On suppose qu'il n'y a pas d' auto-bords dans . $G$

Pour chaque front entre le nœud et dans , soit et , ce qui donne le nombre de chemins à deux sauts entre chaque paire de nœuds et . Puis pour l'arête entre $v_i$ $v_j$ $G$ $E[i,j]=1$ s'il n'y a pas d'arête. Calculer matrice $E[i,j]=0$ $n\times n$ $C[i,j]=\sum_{k=1}^n E[i,k]\cdot E[k,j]$ $v_i$ $v_j$ $v_i$ et dans calculer sinon définir $v_j$ $G$ $D[i,j]=E[i,j]\cdot C[i,j]$ $D[i,j]=\infty$ , qui donne le nombre de triangles dont le bord fait partie (ou l'infini s'il n'y a pas de bord). La multiplication matricielle nécessaire pour calculer coûte (pourrait être calculée plus rapidement en fonction de la rareté de ). $C$ $O(n^3)$ $G$

Calculez maintenant matrice , telle que $n\times n$ $A$ . est tous les chemins les plus courts en $A[i,j]=\min(D[i,j],\min_k(D[i,k]+D[k,j]-E[i,j]))$ $A$ $D$ de longueur jusqu'à deux augmentée pour tenir compte des chemins qui longent les deux bords d'un triangle.

Maintenant, calculez simplement le chemin le plus court entre et dans sur un nouveau graphique dont est la matrice d'adjacence (pondérée) en utilisant Dijkstra (puisque tous les poids de bord sont positifs) c'est-à-dire et déterminez si , où est la fermeture sur le semi-cercle tropical (qui donne la matrice de distance). $v_i$ $v_j$ $G$ $A$ $A^*[i,j]\leq k$ $A^*$

Edgar
la source

La complexité de ce problème de chemin est-elle connue?

Réponses: