Vollständigkeit über Bäume hinweg

Ein Spanning Tree eines Graphen wird als Vollständigkeitsbaum bezeichnet, wenn die Menge seiner Blätter einen vollständigen Untergraphen im Host-Graph induziert. Wie komplex ist es bei einem Graphen und einer ganzen Zahl k zu entscheiden, ob G einen Vollständigkeitsbaum mit höchstens k Blättern enthält?$G$$k$$G$$k$

Ein Grund für diese Frage ist, dass das entsprechende Problem für Unabhängigkeitsbäume NP-vollständig ist. Hier ist ein Unabhängigkeitsbaum ein Spanning Tree, so dass die Menge seiner Blätter eine unabhängige Menge im Host-Diagramm ist.

Ein weiterer Grund ist diese Frage (und die entsprechenden Antworten). Es stellt sich heraus, dass jeder Spannbaum von genau dann ein Vollständigkeitsbaum ist, wenn G ein vollständiger Graph oder ein Zyklus ist. $G$$G$

In einem dreieckfreien Diagramm muss ein Vollständigkeitsbaum ein Hamilton-Zyklus sein (minus einer seiner Kanten). Laut ISGCI ist der Hamilton-Zyklus in dreieckfreien Graphen NP-vollständig. Daher ist es auch wichtig, einen Vollständigkeitsbaum zu finden (unabhängig von einer Einschränkung der maximalen Anzahl von Blättern).

Ich kann David in der Eleganz seiner Antwort nicht schlagen. Aber nachdem ich viel Zeit damit verbracht habe, über dieses Problem nachzudenken, möchte ich Ihnen meine Lösung verraten;)

$k \ge 2$$G$$H$$G_1$$G_2$$Q$$k$$x, x_1, x_2, \ldots, x_{k-1}$$y$$v_1 \in G_1$$v_2 \in G_2$$H$$G_1, G_2, Q$$y$$x$$v_1$$x_1, x_2, \ldots, x_{k-1}$$v_2$$v_1$$G_1$$v_2$$G_2$$y$

$G$$H$$k$