Balanced connected subgraph problem in geometric intersection graphs

DOI10.1007/978-3-030-36412-0_5MaRDI QIDQ2180133zbMATH OpenOpenAlexFDO

Authors Sujoy Bhore, Satyabrata Jana, Supantha Pandit, Sasanka Roy

Publication date 13 May 2020

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

zbMATH Keywords

interval graphscircular-arc graphsfixed-parameter tractabilityNP-hardnesspermutation graphsbalanced connected subgraphcolor-balancedouter-string graphsunit-disk graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We study the Balanced Connected Subgraph(shortly, BCS) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given a vertex-colored graph $G=(V,E)$, where each vertex in $V$ is colored with either ``red or ``blue, the BCS problem seeks a maximum cardinality induced connected subgraph $H$ of $G$ such that $H$ is color-balanced, 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 algorithm for the Steiner Tree problem on both the interval graphs and circular arc graphs, that is used as a subroutine for solving BCS problem on same graph classes. Finally, we present a FPT algorithm for the BCS problem on general graphs.

Recommendations

• Algorithms and hardness results for the maximum balanced connected subgraph problem
• Complexity and inapproximability results for balanced connected subgraph problem
• The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs

Cited in

(9)

• Balanced connected graph partition
• Balanced independent and dominating sets on colored interval graphs
• Complexity and inapproximability results for balanced connected subgraph problem
• Balanced substructures in bicolored graphs
• The balanced connected subgraph problem for geometric intersection graphs
• Balanced substructures in bicolored graphs
• Algorithms and hardness results for the maximum balanced connected subgraph problem
• The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs
• On the hardness of the Balanced Connected Subgraph Problem for families of Regular Graphs

This page was built for publication: Balanced connected subgraph problem in geometric intersection graphs

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