Ist der Schnittpunkt von

Es ist bekannt, dass der Schnittpunkt von drei allgemeinen Matroiden NP-hart ist ( Quelle ), was durch Reduktion aus dem Hamilton-Zyklus erfolgt. Für die Reduzierung werden eine Grafik-Matroide und zwei Konnektivitäts-Matroide verwendet.

Ein spezieller Fall eines Problems, an dem ich arbeite, kann durch Überschneiden mehrerer grafischer Matroiden gelöst werden, aber ich konnte nicht feststellen, ob dieses Problem in P vorliegt.

Frage: Ist es bekannt? Kann mich bitte jemand auf ein Papier oder so verweisen?

( Hinweis: Ich habe diese Frage zur Informatik gestellt und wurde hier verwiesen.)

Ich denke, es ist immer noch NP-vollständig, durch eine Reduktion von Hamilton-Pfaden in zweigeteilten Graphen mit zwei Eckpunkten vom Grad eins und allen anderen Eckpunkten vom Grad drei. (Dies ist genauso, als würde man Hamilton-Zyklen durch eine bestimmte Kante in einem kubischen zweigeteilten Graphen finden - ersetzen Sie die angegebene Kante durch zwei Blätter.)

Um von Hamilton-Pfaden zu Schnittpunkten von Grafik-Matroiden zu gelangen, verwenden Sie eine Grafik-Matroide, um den von Ihnen ausgewählten Untergraphen zu einem übergreifenden Baum (wahr für jeden Pfad) zu zwingen, und zwei weitere Grafik-Matroiden, eine auf jeder Seite der Bipartition, um den Untergraphen zu zwingen haben Grad zwei an jedem Eckpunkt mit Grad drei und eine Kante an jedem Eckpunkt mit Grad eins. Dies sind die grafischen Matroiden eines Graphen mit disjunkten Kopien von für jeden Scheitelpunkt des dritten Grades und K 2 für jeden Scheitelpunkt des ersten Grades.$K_3$$K_2$

Wie wäre es, wenn Sie die Tatsache nutzen, dass die 3-D-Übereinstimmung NP-vollständig ist, um die NP-Vollständigkeit dieses Problems aufzuzeigen? Wir können 3D-Übereinstimmungen einfach als Schnittmenge von 3 Partitionsmatrizen schreiben, und eine Partitionsmatrize ist ein Sonderfall einer Grafikmatrize (betrachten Sie ein Diagramm mit parallelen Kanten).