The Balanced Connected Subgraph Problem: Complexity Results in Bounded-Degree and Bounded-Diameter Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

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

Résumé

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.
Fichier non déposé

Dates et versions

lirmm-02454914 , version 1 (29-01-2020)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More