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
Conference Papers Year : 2019

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

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.
No file

Dates and versions

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

Identifiers

Cite

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⟩
72 View
0 Download

Altmetric

Share

More