Paper Info
Title
The Balanced Connected Subgraph Problem
Abstract
The problem of computing induced subgraphs that satisfy some specified restrictions arises in various applications of graph algorithms and has been well studied. In this paper, we consider the following Balanced Connected Subgraph (shortly, BCS) problem. The input is a graph G = (V, E), with each vertex in the set V having an assigned color, "red" or "blue". We seek a maximum-cardinality subset V ' subset of V of vertices that is color-balanced (having exactly vertical bar V 'vertical bar/2 red nodes and vertical bar V 'vertical bar/2 blue nodes), such that the subgraph induced by the vertex set V ' in G is connected. We show that the BCS problem is NP-hard, even for bipartite graphs G (with red/blue color assignment not necessarily being a proper 2-coloring). Further, we consider this problem for various classes of the input graph G, including, e.g., planar graphs, chordal graphs, trees, split graphs, bipartite graphs with a proper red/blue 2-coloring, and graphs with diameter 2. For each of these classes either we prove NP-hardness or design a polynomial time algorithm.
Year
DOI
Venue
2019
10.1007/978-3-030-11509-8_17
ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2019
Keywords
DocType
Volume
Balanced connected subgraph, Trees, Split graphs, Chordal graphs, Planar graphs, Bipartite graphs, NP-hard, Color-balanced
Conference
11394
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
8
6
Name
Order
Citations
PageRank
Sujoy Bhore102.03
Sourav Chakraborty238149.27
Satyabrata Jana311.70
Joseph S.B. Mitchell44329428.84
Supantha Pandit505.41
Sasanka Roy63113.37