Ning Chen, Roee Engelberg, Cam Thach Nguyen, Prasad Raghavendra, Atri Rudra and Gyanit Singh

A *star* graph is a tree of diameter at most two.
A *star forest* is a graph that consists of node-disjoint
star graphs.
In the spanning star forest problem, given an unweighted graph *G*,
the objective is to find a star
forest that contains all the vertices of *G* and has
the maximum number of edges. This problem is
the complement of the dominating set problem in the following sense:
On a graph with *n* vertices, the size of the maximum spanning star forest is
equal to *n* minus the size of the minimum dominating set.

We present a *0.71*-approximation algorithm for this problem,
improving upon the approximation factor of *0.6* of Nguyen et
al. We also present a *0.64*-approximation algorithm
for the problem on node-weighted graphs. Our algorithms use an new non-linear
randomized rounding technique for linear programs, which could be useful in other
application. Finally, we present
improved hardness of approximation results for the weighted versions
of the problem.