4.13.9 k-SPANNING TREE

Definition

Given an undirected graph G = (V, E), there exists a spanning tree T in G, in which each node has degree ≤ k, if such tree exists.

Polynomial Certifier

Given an undirected graph G = (V, E), does there exist a spanning tree T in G, in which each node has degree ≤ k, if such tree exists.

• Input: Given an undirected graph G and integer k.
• Certificate: A tree, T ⊆ V .
• Certifier: We can use DFS to traverse through T, and make sure each node has degree k.
• Time Complexity: In the worst case, T = G, the running time of DFS is O(m + n).