Balanced Connected Subgraph Problem in Geometric Intersection Graphs

Sujoy Bhore, Satyabrata Jana, Supantha Pandit, Sasanka Roy

Introduction

The Balanced Connected Subgraph (BCS) problem is a fundamental challenge in graph theory with significant practical implications. Given a graph where vertices are colored (e.g., red and blue), the goal is to find the largest connected subgraph that contains an equal number of vertices of each color. This problem models scenarios in bioinformatics, such as identifying balanced metabolic pathways or protein-protein interaction motifs where specific stoichiometric ratios are required for biological function.

While the BCS problem is known to be NP-hard on general graphs, this research explores whether the inherent structure of geometric intersection graphs—where nodes represent geometric objects and edges represent their overlaps—can simplify the problem.

The Dimensionality Divide

A primary finding of this work is a sharp complexity boundary between one-dimensional and two-dimensional geometric structures. The researchers discovered that the BCS problem is solvable in polynomial time for 1D-like graphs, such as interval and permutation graphs, but becomes computationally intractable (NP-hard) as soon as the objects are embedded in a 2D plane.

Hardness in Two Dimensions

To establish NP-hardness for 2D geometric graphs (including unit disks, unit squares, and grid graphs), the authors utilized a reduction from the Rectilinear Steiner Tree (RST) problem. The reduction involves constructing complex "gadgets" on a grid that translate the connectivity requirements of a Steiner tree into the balance and connectivity requirements of the BCS problem.

Gadgets used in the NP-hardness reduction from Rectilinear Steiner Tree, showing how connectivity and balance are maintained.

These gadgets ensure that any maximum balanced connected subgraph must correspond to an optimal solution for the original RST instance. By further embedding these grid structures into geometric shapes, the authors proved that the problem remains hard even for simple 2D objects like unit squares.

Embedding the grid gadget into a geometric intersection graph of unit squares.

Efficient Algorithms for 1D Structures

In contrast to the 2D case, the paper presents efficient polynomial-time algorithms for several 1D graph families:

  • Interval Graphs: Solvable in $O(n^4 \log n)$ time using a greedy approach to the Steiner Tree problem as a sub-routine.
  • Permutation Graphs: Solvable in $O(n^6)$ time.
  • Circular-Arc Graphs: Solvable in $O(n^6 \log n)$ time.

The core insight for these algorithms is that connectivity in 1D-like graphs is more constrained, allowing for dynamic programming or greedy strategies that can efficiently track the "balance delta" (the difference between red and blue nodes) across the graph.

General Graphs and Fixed-Parameter Tractability

For general graphs where the problem is NP-hard, the authors developed a Fixed-Parameter Tractable (FPT) algorithm. By parameterizing the problem by the size of the target subgraph $k$, they achieved a running time of $2^{O(k)} n^2 \log n$. This is accomplished through a "color-coding" technique combined with a novel "batch procedure" that efficiently manages connected components while maintaining the required color balance.

Conclusion and Future Work

This research provides a comprehensive map of the complexity of the BCS problem in geometric settings. While the transition from 1D to 2D marks a significant jump in difficulty, the FPT results offer a path forward for solving the problem on general graphs when the desired motif is relatively small. Future research may focus on developing approximation algorithms for the NP-hard 2D cases or optimizing the high-degree polynomial exponents found in the 1D algorithms.

Summary updated

Abstract

We study the (shortly, ) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given a graph \(G=(V,E)\), where each vertex in V is colored with either “ ” or “ ”, the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is , i.e., H contains an equal number of red and blue vertices. We study the computational complexity landscape of the BCS problem while considering geometric intersection graphs. On one hand, we prove that the BCS problem is NP-hard on the unit disk, outer-string, complete grid, and unit square graphs. On the other hand, we design polynomial-time algorithms for the BCS problem on interval, circular-arc and permutation graphs. In particular, we give algorithms for the problem on both interval and circular-arc graphs, and those algorithms are used as subroutines for solving the BCS problem on the same classes of graphs. Finally, we present a FPT algorithm for the BCS problem on general graphs.
BibTeX
@inproceedings{bhore2019balanced,
  author = {Sujoy Bhore and Satyabrata Jana and Supantha Pandit and Sasanka Roy},
  title = {{Balanced Connected Subgraph Problem in Geometric Intersection Graphs}},
  booktitle = {COCOA},
  year = {2019},
  url = {https://openreview.net/forum?id=OBeKDeCZTl},
}
Figure