Combinatorics for smaller kernels: The differential of a graph

Let G=(V,E)G=(V,E) be a graph of order n   and let B(D)B(D) be the set of vertices in V∖DV∖D that have a neighbor in the vertex set D. The differential of D   is defined as ∂(D)=|B(D)|−|D|∂(D)=|B(D)|−|D| and the differential of a graph G  , written ∂(G)∂(G), is equal to max⁡{∂(D):D⊆V}max⁡{∂(D):D⊆V}. If G   is connected and n≥3n≥3, ∂(G)≥n/5∂(G)≥n/5 is known. This immediately leads to a linear vertex kernel result (in the terminology of parameterized complexity) for the problem of deciding whether ∂(G)≥k∂(G)≥k, taking k   as the parameter. We then establish a new combinatorial result which establishes that ∂(G)≥n/4∂(G)≥n/4 if G   is a connected graph of order n≥6n≥6 and if G   contains no induced path of five vertices whose midpoint is a cut vertex and whose endpoints have degree one. This technical combinatorial theorem can be used to derive an even smaller linear vertex kernel for general graphs. Also, we show that the related maximization problem allows for a polynomial-time factor-14 approximation algorithm.