Intégralité couvrant les arbres

Un arbre couvrant un graphe est appelé arbre d'exhaustivité si l'ensemble de ses feuilles induit un sous-graphe complet dans le graphe hôte. Étant donné un graphique et un entier k , quelle est la complexité de décider si G contient un arbre d'exhaustivité avec au plus k feuilles?$G$$k$$G$$k$

Une raison pour poser cette question est que le problème correspondant pour les arbres d'indépendance est NP-complet, ici un arbre d'indépendance est un arbre couvrant tel que l'ensemble de ses feuilles est un ensemble indépendant dans le graphe hôte.

Une autre raison est cette question (et les réponses correspondantes). Il s'avère que tout arbre couvrant de est un arbre d'exhaustivité si et seulement si G est un graphe complet ou un cycle. $G$$G$

Dans un graphique sans triangle, un arbre d'exhaustivité doit être un cycle hamiltonien (moins l'une de ses arêtes). L'ISGCI indique que le cycle hamiltonien est NP-complet dans les graphiques sans triangle. Par conséquent, il en va de même pour trouver un arbre d'exhaustivité (indépendamment de toute restriction sur le nombre maximum de feuilles).

Je ne peux pas battre David dans l'élégance de sa réponse. Mais après avoir passé beaucoup de temps à réfléchir à ce problème, je voudrais quand même vous trahir ma solution;)

$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$