On maximum leaf trees and connections to connected maximum cut problems

•We obtain the first logarithmic approximation algorithm for the Maximum Leaf Tree problem with general weights on directed and undirected graphs.•We show that an α-approximation algorithm for the weighted Maximum Leaf Tree problem leads to an Ω(α)-approximation algorithm for the Connected Maximum Cut problem on general weighted graphs.•Combined with the previous result, we obtain a logarithmic approximation for the Connected Maximum Cut problem, thus improving upon the Ω(1log2⁡n)-approximation obtained by Hajiaghayi et al. (ESA 2015).

In an instance of the (directed) Max Leaf Tree (MLT) problem we are given a vertex-weighted (di)graph G(V,E,w) and the goal is to compute a subtree with maximum weight on the leaves. The weighted Connected Max Cut (CMC) problem takes in an undirected edge-weighted graph G(V,E,w) and seeks a subset S⊆V such that the induced graph G[S] is connected and ∑e∈δ(S)w(e) is maximized.We obtain a constant approximation algorithm for MLT when the weights are chosen from {0,1}, which in turn implies a Ω(1/log⁡n) approximation for the general case. We show that the MLT and CMC problems are related and use the algorithm for MLT to improve the factor for CMC from Ω(1/log2⁡n) (Hajiaghayi et al., ESA 2015) to Ω(1/log⁡n).