Complexity and inapproximability results for balanced connected subgraph problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
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.
Fichier principal
Vignette du fichier
S0304397521004114.pdf (663.59 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03475313 , version 1 (16-10-2023)

Licence

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⟩
43 View
22 Download

Altmetric

Share

More