Finden von Min-Max-Vertex-disjunkten Pfaden mit einer gemeinsamen Quelle in planaren Graphen

Finden Sie bei einem planaren ungewichteten Graphen und einer Sammlung von Scheitelpunktpaaren ( k ≥ 2 ist eine Konstante) k vertex-disjunkte (außer Quell-) Pfade von s nach t i so, dass die Länge des längsten Pfades minimiert wird.$(s,t_1),\dots,(s,t_k)$$k\ge2$$k$$s$$t_i$

Frage: Gibt es einen Polynom-Zeit-Algorithmus für das Problem?

Einige verwandte Ergebnisse:

• wenn nicht behoben ist, ist das Problem NP-hart, selbst wenn t 1 = ⋯ = t k ;$k$$t_1=\dots=t_k$
• Wenn der Eingabegraph gewichtet ist und die Quellen der Pfade nicht zusammenfallen, dh die Pfade sind das Problem selbst für k = 2 NP-schwer ;$(s_1,t_1),\dots,(s_k,t_k)$$k=2$

• Ein Problem mit einem anderen Ziel, nämlich der Minimierung der Summe der Pfadlängen, ist

  • lösbar mit dem Minimum-Cost-Flow-Algorithmus für übereinstimmende Quellen;
  • NP-hart für nicht übereinstimmende Quellen und allgemeines ;$k$
  • offen für nicht übereinstimmende Quellen und Konstante .$k$

Dies ist nicht genau das, was Sie gefragt haben, aber das Problem ist NP-vollständig, wenn k keine Konstante ist, sondern Teil der Eingabe.

Dies folgt aus dem Beweis von Satz 1 in van der Holst und de Pina [HP02], der besagt: Wenn ein planarer Graph G , verschiedene Eckpunkte s und t in G und positive ganze Zahlen k und b gegeben sind , ist die Entscheidung NP-vollständig ob es k paarweise intern vertex-disjunkte Pfade zwischen s und t mit jeweils höchstens b Länge gibt .

Beachten Sie, dass sich das Problem in der Aussage von Satz 1 in zweierlei Hinsicht von Ihrem unterscheidet. Ein Unterschied besteht, wie bereits erwähnt, darin, dass k als Teil der Eingabe angegeben wird. Das andere ist, dass das Problem in [HP02] Pfade mit gemeinsamen Endpunkten anstelle von Pfaden mit einer gemeinsamen Quelle und verschiedenen Senken sind. Ich weiß nicht, wie ich den ersten Unterschied beheben soll. Der Unterschied ist so groß, dass wir wahrscheinlich einen völlig anderen Beweis benötigen, um k zu reparieren . Aber ich weiß zumindest, wie ich den zweiten Unterschied beheben kann.

Der Beweis von Satz 1 in [HP02] ergibt eine Reduktion von 3SAT. Diese Reduktion hat die folgende Eigenschaft: In dem durch die Reduktion konstruierten Fall ( G , s , t , k , b ) ist der Grad des Scheitelpunkts t immer gleich k . Sei t ₁ ,…, t _k die k Nachbarn von t . Anstatt zu fragen, ob es k paarweise intern vertex-disjunkte Pfade zwischen s und t gibt, die jeweils höchstens b lang sindkönnen wir gleichermaßen fragen, ob es paarweise Vertex-Disjoint-außer-Source-Pfade P ₁ ,…, P _{k gibt,} so dass jedes P _i ein Pfad zwischen s und t _{i mit} einer Länge von höchstens b −1 ist.

[HP02] H. van der Holst und JC de Pina. Längenbegrenzte disjunkte Pfade in planaren Graphen. Discrete Applied Mathematics , 120 (1–3): 251–261, August 2002. http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3