تقرير
Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem
| العنوان: | Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem |
|---|---|
| المؤلفون: | Kobayashi, Yasuaki, Kojima, Kensuke, Matsubara, Norihide, Sone, Taiga, Yamamoto, Akihiro |
| سنة النشر: | 2019 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics |
| الوصف: | 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. Comment: accepted at COCOA 2019 |
| نوع الوثيقة: | Working Paper |
| الوصول الحر: | http://arxiv.org/abs/1910.07305Test |
| رقم الانضمام: | edsarx.1910.07305 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |