Computing the differential of a graph: Hardness, approximability and exact algorithms

We are studying computational complexity aspects of the differential of a graph, a graph parameter previously introduced to model ways of influencing a network. We obtain NP hardness results also for very special graph classes, such as split graphs and cubic graphs. This motivates to further classify this problem in terms of approximability. Here, one of our results shows MAXSNP completeness for the corresponding maximization problem on subcubic graphs. Moreover, we also provide a Measure & Conquer analysis for an exact moderately exponential-time algorithm that computes that graph parameter in time O(1.755n)O(1.755n) on a graph of order nn.