Kompletność obejmująca drzewa

Drzewo opinające wykresu nazywane jest drzewem kompletności, jeśli zbiór jego liści indukuje całkowity podrozdział na grafie gospodarza. Biorąc pod uwagę wykres i liczbę całkowitą , jaka jest złożoność decyzji, czy zawiera drzewo kompletności z co najwyżej liści?$G$$k$$G$$k$

Powodem zadawania tego pytania jest to, że odpowiadającym problemem dla drzew niezależności jest NP-zupełne, tutaj drzewo niezależności jest drzewem opinającym, tak że zbiór jego liści jest niezależnym zbiorem na grafie hosta.

Innym powodem jest to pytanie (i odpowiadające odpowiedzi). Okazuje się, że każde drzewo rozpinające jest drzewem kompletności wtedy i tylko wtedy, gdy jest kompletnym wykresem lub cyklem. $G$$G$

Na wykresie bez trójkąta drzewem kompletności musi być cykl hamiltonowski (minus jedna z jego krawędzi). ISGCI twierdzi, że cykl Hamiltonian jest kompletny z NP na grafach bez trójkątów. Dlatego też znajduje się drzewo kompletności (bez względu na jakiekolwiek ograniczenie maksymalnej liczby liści).

Nie mogę pokonać Davida w elegancji jego odpowiedzi. Ale po spędzeniu dużo czasu na myśleniu o tym problemie chciałbym wam zdradzić moje rozwiązanie;)

Niech będzie stałym intergerem. Biorąc pod uwagę G , skonstruuj H w następujący sposób: weź dwie kopie G 1 , G 2 i klikę Q na k wierzchołków x , x 1 , x 2 , … , x k - 1 , nowy wierzchołek y , napraw wierzchołek v 1 ∈ G 1 i wierzchołek v 2 ∈ G 2 . H otrzymuje się z$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$ i y łącząc x z v 1 , łącząc x 1 , x 2 , … , x k - 1 z v 2 i łącząc wszystkich sąsiadów v 1 w G 1 i wszystkich sąsiadów v 2 w G 2 do y .$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$

Następnie można łatwo zauważyć, że ma cykl hamiltonowski, tylko wtedy, gdy H ma drzewo kompletności z co najwyżej k liści.$G$$H$$k$