The balanced connected subgraph problem
| Autor: | Sasanka Roy, Supantha Pandit, Satyabrata Jana, Sujoy Bhore, Sourav Chakraborty, Joseph S. B. Mitchell |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Applied Mathematics Vertex connectivity Planar graph Vertex (geometry) Combinatorics Set (abstract data type) symbols.namesake Chordal graph TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY FOS: Mathematics symbols Bipartite graph Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Graph algorithms Time complexity Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Applied Mathematics. 319:111-120 |
| ISSN: | 0166-218X |
| Popis: | 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'\subseteq V$ of vertices that is color-balanced (having exactly $|V'|/2$ red nodes and $|V'|/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. 15 pages, 3 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect