Algorithms and hardness results for the maximum balanced connected subgraph problem

DOI10.1007/978-3-030-36412-0_24MaRDI QIDQ2180163zbMATH OpenOpenAlexFDO

Authors Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara, Taiga Sone, Akihiro Yamamoto

Publication date 13 May 2020

Full work available at URL https://arxiv.org/abs/1910.07305

zbMATH Keywords

balanced connected subgraphexact exponential-time algorithminterval graphtreetreewidth

Mathematics Subject Classification ID

Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: The Balanced Connected Subgraph problem (BCS) was recently introduced by Bhore et al. (CALDAM 2019). In this problem, we are given a graph $G$ whose vertices are colored by red or blue. The goal is to find a maximum connected subgraph of $G$ having the same number of blue vertices and red vertices. They showed that this problem is NP-hard even on planar graphs, bipartite graphs, and chordal graphs. They also gave some positive results: BCS can be solved in $O(n^3)$ time for trees and $O(n+m)$ time for split graphs and properly colored bipartite graphs, where $n$ is the number of vertices and $m$ is the number of edges. In this paper, we show that BCS can be solved in $O(n^2)$ time for trees and $O(n^3)$ time for interval graphs. The former result can be extended to bounded treewidth graphs. We also consider a weighted version of BCS (WBCS). We prove that this variant is weakly NP-hard even on star graphs and strongly NP-hard even on split graphs and properly colored bipartite graphs, whereas the unweighted counterpart is tractable on those graph classes. Finally, we consider an exact exponential-time algorithm for general graphs. We show that BCS can be solved in $2^{n/2}{n}^{O(1)}$ time. This algorithm is based on a variant of Dreyfus-Wagner algorithm for the Steiner tree problem.

Recommendations

• Complexity and inapproximability results for balanced connected subgraph problem
• The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs
• Balanced connected subgraph problem in geometric intersection graphs

Cited in

(9)

• The balanced connected subgraph problem for geometric intersection graphs
• Balanced connected subgraph problem in geometric intersection graphs
• The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs
• Complexity and inapproximability results for balanced connected subgraph problem
• The balance problem of min-max systems is co-nNP hard
• A matheuristic approach for the maximum balanced subgraph of a signed graph
• On the hardness of the Balanced Connected Subgraph Problem for families of Regular Graphs
• Balanced substructures in bicolored graphs
• Balanced substructures in bicolored graphs

This page was built for publication: Algorithms and hardness results for the maximum balanced connected subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2180163)