Skip to Main content Skip to Navigation
Conference papers

The Balanced Connected Subgraph Problem: Complexity Results in Bounded-Degree and Bounded-Diameter Graphs

Benoit Darties 1 Rodolphe Giroudeau 1 Jean-Claude König 1 Valentin Pollet 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02454914
Contributor : Rodolphe Giroudeau <>
Submitted on : Wednesday, January 29, 2020 - 11:04:50 AM
Last modification on : Tuesday, February 4, 2020 - 1:34:20 AM

Identifiers

Collections

Citation

Benoit Darties, Rodolphe Giroudeau, Jean-Claude König, Valentin Pollet. The Balanced Connected Subgraph Problem: Complexity Results in Bounded-Degree and Bounded-Diameter Graphs. 13th International Conference on Combinatorial Optimization and Applications (COCOA), Dec 2019, Xiamen, China. pp.449-460, ⟨10.1007/978-3-030-36412-0_36⟩. ⟨lirmm-02454914⟩

Share

Metrics

Record views

59