We present new complexity results for the Balanced Connected Subgraph (BCS) problem. Given a graph whose vertices are colored either blue or red, find the largest connected subgraph containing as many red vertices as blue vertices. We establish the NP-completeness of the decision variant of this problem in bounded-diameter and bounded-degree graphs: bipartite graphs of diameter four, graphs of diameter three and bipartite cubic graphs. BCS being polynomially solvable in graphs of diameter two and maximum degree two, our results close some of the existing gaps in the complexity landscape.
展开▼
