Complexity and inapproximability results for balanced connected subgraph problem

This work is devoted to the study of the Balanced Connected Subgraph Problem (BCS) from a complexity, inapproximability and approximation point of view. The input is a graph G = ( V , E ) , with each vertex having been colored, “red” or “blue”; the goal is to find a maximum connected subgraph G ′ = ( V ′ , E ′ ) from G that is color-balanced (having exactly | V ′ | / 2 red vertices and | V ′ | / 2 blue vertices). This problem is known to be NP -complete in general but polynomial in paths and trees. We propose a polynomial-time algorithm for block graph. We propose some complexity results for bounded-degree or bounded-diameter graphs, and also for bipartite graphs. We also propose inapproximability results for some graph classes, including chordal, planar, or subcubic graphs.