Complexity and inapproximability results for balanced connected subgraph problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Theoretical Computer Science Year : 2021

Complexity and inapproximability results for balanced connected subgraph problem

Abstract

This work is devoted to the study of the Balanced Connected Subgraph Problem (BCS) from a complexity, inapproximability and approximation point of view. The input is a graph G=(V,E), with each vertex having been colored, “red” or “blue”; the goal is to find a maximum connected subgraph G′=(V′,E′) from G that is color-balanced (having exactly |V′|/2 red vertices and |V′|/2 blue vertices). This problem is known to be NP-complete in general but polynomial in paths and trees. We propose a polynomial-time algorithm for block graph. We propose some complexity results for bounded-degree or bounded-diameter graphs, and also for bipartite graphs. We also propose inapproximability results for some graph classes, including chordal, planar, or subcubic graphs.

Dates and versions

lirmm-03475313 , version 1 (10-12-2021)

Identifiers

Cite

Timothée Martinod, Valentin Pollet, Benoit Darties, Rodolphe Giroudeau, Jean-Claude König. Complexity and inapproximability results for balanced connected subgraph problem. Theoretical Computer Science, 2021, 886, pp.69-83. ⟨10.1016/j.tcs.2021.07.010⟩. ⟨lirmm-03475313⟩
15 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More