Paired-Domination Problem on Graph Classes

View Statistics Email Alert RSS Feed

Information

Details

Project title

Code/計畫編號

MOST107-2221-E019-016

Translated Name/計畫中文名

各種圖類上的成對支配點問題

Project Coordinator/計畫主持人

Ching-Chi Lin

Funding Organization/主管機關

National Science and Technology Council

Department/Unit

Department of Computer Science and Engineering

Website

https://www.grb.gov.tw/search/planDetail?id=12675567

Year

2018

Start date/計畫起

01-08-2018

Expected Completion/計畫迄

31-07-2019

Bugetid/研究經費

646千元

ResearchField/研究領域

資訊科學--軟體

給定一個圖 G = (V,E)，對於一個支配點問題 (domination problem)，我們希望在 G 中找一個元素個數為最少的支配點集合 S，使得每個不在 S 中的點都與 S 相鄰。如果 S 的誘導子圖 G[S] 包含一個完美匹配 (perfect matching)，則我們稱 S 是 G 的“成對支配點集合”(paired-dominating set)。對於一個成對支配點問題 (paired-domination problem) 我們希望在 G 中找一個成對支配點集合使得集合的元素個數為最少。如果每一個在圖上的點 v，都有一個權重 w(v)，則加權成對支配點問題是要找一個成對支配點集合 S，使得 S 中元素權重總和為最小。在之前的科技部計畫中 [55,56]，我們已經對成對支配點問題做深入的研究與探討，並且在圓弧圖 (circular-arc graph) 以及加權圓弧圖上分別得到時間複雜度為 O(n) 以及 O(n + m) 時間的演算法。圓弧圖上的研究成果目前已經發表在 Theoretical Computer Science [57]。延續之前的研究成果，在本計畫中，我們將更深入探討加權圖上的成對支配點問題。Chen 等人 [18,19] 在 weighted tree graphs 以及 block graphs 上分別提出了時間複雜度為 O(n) 以及 O(n + m) 的演算法。在本計畫中，我們將使用 dynamic-programming 演算法技巧改進 Chen 等人的研究成果，在加權的 block graphs 和 distance-hereditary graphs 預計分別提出時間複雜度為 O(n + m) 和 O(n^2)的演算法。同時也計畫證明成對支配點問題在 circle graphs 上為 NP-complete。另外， Chen 等人 [18] 同時也在一般圖上提出一個 ln(2△(G)) + 1 的近似演算法並且證明這一個問題沒有 PTAS。根據以上設計演算法所得到的知識與經驗，我們希望能在一般圖 (general graph) 上找到常數倍數的近似演算法，同時希望證明在平面圖 (planar graph) 上的成對支配問題為 NP-complete，並且設計此問題在平面圖上的近似演算法。 Given a graph G = (V,E), the domination problem is to find a minimum size vertex subset S such that every vertex not in S is adjacent to a vertex in S. A dominating set S of G is called a paired-dominating set if the induced subgraph G[S] contains a perfect matching. The paired-domination problem involves finding a paired-dominating set S of G such that the cardinality of S is minimized. Suppose that, for each v, we have a weight w(v) specifying the cost for adding v to S. The weighted paired-domination problem is to find a paired-dominating set S such that the sum of the weight of each v in S is minimized.In the previous NSC projects [55,56], we have studied the paired-domination problem and proposed algorithms for circular-arc graphs and weighted circular-arc graphs that run in O(n) and O(n+m) time, respectively. The former results for circular-arc graphs have been published on Theoretical Computer Science [57]. Recently, many studies have been made for this problem in proving NP-completeness, providing approximation algorithms, and finding polynomial-time algorithms on some special classes of graphs. Particularly, Chen et al. introduced an O(n)-time algorithm for weighted tree graphs [18], and an O(m+n)-time algorithm for block graphs [19]. In this project, we plan to propose O(n+m)-time and O(n^2)-time algorithms for the weighted paired-domination problem on block graphs and distance-hereditary graphs, respectively, using dynamic-programming method, which strengthens the results in [18,19]. Also, we plan to prove that the problem is NP-complete on circle graphs.Also in [18], Chen et al. proposed an approximation algorithm with ratio ln(2△(G)) + 1 for general graphs and showed that the problemis APX-complete, i.e., has no PTAS. Thus, based on the experience above, we will also try to develop an approximation algorithm for general graphs with constant ratio. Meanwhile, it would be desirable to show that the problem remains NP-complete in planar graphs and design an approximation algorithm.

Keyword(s)

成對支配點問題
加權圖
完美匹配
誘導子圖
圖論演算法
paired-domination problem
weighted graph
perfect matching
graph algorithm
induced subgraph

DSpace CRIS

Paired-Domination Problem on Graph Classes

Details

Description