Give 1-approximation algorithm $Z-Tree$

54 Views Asked by At

$G$ = ($V$,$E$) is a complete graph, $X$ is a subset of $V$, and every edge satisfies the triangle inequality property. $X$-spanning tree is a sub-graph of $G$ that is a tree whose vertex set is precisely $X$. An $X$-extended spanning tree is a subgraph of $G$ that is a tree containing all vertices of $X$ and $0$ or more vertices of $V$ - $X$. The cost of a tree is the sum of the costs of the edges in the tree.

Given problem $Z-Tree$:

Input: A complete graph $G$, a set $X$ which is a subset of $V$, and positive weights on the edges satisfying the triangle inequality

Output: An $X$-extended spanning tree of $G$ of minimum cost.

$Z-Tree$ is known to be NP-hard. I'm kinda struggling to provide a $1$-approximation algorithm for $Z-Tree$