Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem

10/16/2019
by   Yasuaki Kobayashi, et al.
0

The Balanced Connected Subgraph problem (BCS) was recently introduced by Bhore et al. (CALDAM 2019). In this problem, we are given a graph G whose vertices are colored by red or blue. The goal is to find a maximum connected subgraph of G having the same number of blue vertices and red vertices. They showed that this problem is NP-hard even on planar graphs, bipartite graphs, and chordal graphs. They also gave some positive results: BCS can be solved in O(n^3) time for trees and O(n + m) time for split graphs and properly colored bipartite graphs, where n is the number of vertices and m is the number of edges. In this paper, we show that BCS can be solved in O(n^2) time for trees and O(n^3) time for interval graphs. The former result can be extended to bounded treewidth graphs. We also consider a weighted version of BCS (WBCS). We prove that this variant is weakly NP-hard even on star graphs and strongly NP-hard even on split graphs and properly colored bipartite graphs, whereas the unweighted counterpart is tractable on those graph classes. Finally, we consider an exact exponential-time algorithm for general graphs. We show that BCS can be solved in 2^n/2n^O(1) time. This algorithm is based on a variant of Dreyfus-Wagner algorithm for the Steiner tree problem.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset