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 (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 |V '|/2 red vertices and |V '|/2 blue vertices), 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 on various graph classes, 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 we either prove NP-hardness or design a polynomial time algorithm.(c) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2022
10.1016/j.dam.2020.12.030
DISCRETE APPLIED MATHEMATICS
Keywords
DocType
Volume
Balanced connected subgraph, Trees, Split graphs, Chordal graphs, Planar graphs, Bipartite graphs, Polynomial algorithms, NP-hard
Journal
319
ISSN
Citations 
PageRank 
0166-218X
0
0.34
References 
Authors
0
6
Name
Order
Citations
PageRank
Sujoy Bhore100.34
Sourav Chakraborty238149.27
Satyabrata Jana300.68
Joseph S.B. Mitchell44329428.84
Supantha Pandit501.69
Sasanka Roy600.68