Fügen Sie eine Übereinstimmung zu einem Hamilton-Pfad hinzu, um den maximalen Abstand zwischen bestimmten Scheitelpunktpaaren zu verringern

14

Was ist die Komplexität des folgenden Problems?

Eingabe :

  • H einHamilton-PfadinKn
  • eine Teilmenge von KnotenpaarenR[n]2
  • eine positive ganze Zahl k

Abfrage : Gibt es einen passenden derart , daß für jeden ( v , u ) R , d G ( v , u ) k ? (wobei G = ( [ n ] , M H ) )M(v,u)RdG(v,u)k
G=([n],MH)

Ich habe mit einem Freund über dieses Problem gesprochen. Mein Freund glaubt, das Problem liege in der Polynomzeit. Ich denke es ist NP-komplett.

pfim
quelle
11
Sie können dies weiter vereinfachen, zumindest in Bezug auf die Darstellung. Sie erhalten , einen Pfad mit n Eckpunkten und eine Sammlung R von Paaren dieser Eckpunkte. Sie möchten den Pfad mit einer Übereinstimmung erweitern, sodass der Abstand zwischen einem Paar in R höchstens k beträgt . knRRk
Sasho Nikolov
Ich denke, diese Formulierung kann nach meiner letzten Bearbeitung verwirrend sein, um einige Unklarheiten zu beseitigen.
Pfim
1
Meine Interpretation ist richtig, nicht wahr?
Sasho Nikolov
Ich habe eine Änderung vorgenommen, um die Problemstellung strenger zu formulieren. Ich denke, dies kann weiter vereinfacht werden, da Sie einfach annehmen können, dass H der Hamilton-Pfad 1-2-3-4-5 ...- n ohne Verlust der Allgemeinheit ist. Also brauchst du nur . n
Kaveh

Antworten:

1

Diese Antwort ist falsch .

Dein Freund hat recht. Ihr Problem (wie von Sasho interpretiert) schränkt die Kardinalität des übereinstimmenden . Wählen Sie daher C , um eine Übereinstimmung zwischen den Paaren in R zu erhalten . Dann ist für jede positive ganze Zahl k der Abstand zwischen jedem Paar in R kleiner als k .CCRkRk

Ihr Problem wird interessant, wenn Sie Pfade zwingen, Kanten sowohl aus dem übereinstimmenden als auch aus dem Pfad P zu enthalten .CP

Mohammad Al-Turkistany
quelle
Was meinst du mit "Matching zwischen den Paaren in "? R
Emil Jeřábek unterstützt Monica am
@ EmilJeřábek Es bedeutet, die Knoten jedes Paares in durch eine Kante zu verbinden. Also ist C nur R mit einer Kante, die jedes Paar verbindet. Dies entspricht den Pfad zu vermehren P mit einem perfekten Marschieren auf den Paare von R . RCRPR
Mohammad Al-Turkistany
1
Das scheint mir nicht viel Sinn zu machen. Was ist, wenn kein Matching ist? Angenommen, wenn R die Paare ( 1 , 2 ) und ( 1 , 3 ) enthält , wie wählen Sie C aus ? RR(1,2)(1,3)C
Emil Jeřábek unterstützt Monica am
@ EmilJeřábek Ja. Ihr Punkt ist gültig. Ich werde meine Antwort bearbeiten.
Mohammad Al-Turkistany
@pfim Kann der kürzeste Pfad nur mit Kanten von ? C
Mohammad Al-Turkistany
0

UPDATE: Die Antwort unten ist nicht korrekt, weil ich fälschlicherweise angenommen habe, dass der Hamilton-Pfad in einem beliebigen Graphen liegt, nicht in . Ich lasse es unberührt, vielleicht kann ich es reparieren oder es gibt einige Hinweise für eine andere Antwort.Kn

Ich denke es ist NP-komplett. Dies ist eine sehr informelle / schnelle Reduzierungsidee von 3SAT

Für jede Variable füge ich ein "variables Gadget" hinzu mit:xi

  • drei Knoten Xi,+Xi,Xi
  • zwei variable Kanten und ( X i , - X i )(Xi,+Xi)(Xi,Xi)

Fügen Sie einen Quellknoten und verbinden Sie ihn mit allen Variablen X i .SXi

Fügen Sie für jede Klausel einen Knoten C j hinzu und verbinden Sie ihn mit den entsprechenden Variablen + X i oder - X i , die die Klausel bilden.CjCj+XiXi

(+x1x2x3)(x2x3x4)

enter image description here

R(S,C1),(S,C2),...

P(Xi,+Xi)(Xi,Xi) (in the picture above the blue edges represent the edges that we include in P).

At this point, the initial formula is satisfiable if and only if the shortest path from S to each clause node Cj is not greater than three. Indeed to reach a clause from S in three steps we must traverse at least one variable Xi: SXi±XiCj. So we must traverse one of the two edges: Xi+Xi or XiXi) and include it into C (because by construction it's not part of P). But both cannot be included, because they share a vertex.

But we're not sure that we can build a simple path P that includes all the blue edges because some nodes have more than one incident blue edge.

To fix this we replace each node with multiple incident blue edges, with a tree that contains only pairs of incident blue edges that will be included in P and edges that separate them and that should be included in C to reach the clause nodes:

enter image description here

The original graph becomes:

enter image description here

Each tree should have the same depth (we just can pick the max of the depth required for all the clauses/variables/S); and we must increase the value of K accordingly (the number of steps to reach Cj from S).

We can include in C all the needed (not blue) edges required to reach the clause nodes because they share no vertex.

Furthermore with this construction we are able to build a simple path P that traverse each vertex and each blue edge, just add extra nodes to avoid shortcuts between the clauses or variables:

enter image description here

Marzio De Biasi
quelle
Trying to build a path that contains all the blue edges worries me: some vertices have more than 2 blue edges incident on them, so there can't be any single simple path including all the blue edges.
Mikhail Rudoy
Ok, thank you ... I completely forgot what is a simple path :-( ... now it should be fixed.
Marzio De Biasi
This post on math.SE suggests that the problem may not be NP-complete. It could be intractable but solvable in quasipolynomial time math.stackexchange.com/questions/2218929/…
Mohammad Al-Turkistany
@MohammadAl-Turkistany: do you see a flaw in the current version of the answer?
Marzio De Biasi
No, I don't see any obvious flaw.
Mohammad Al-Turkistany