2019-10-14T16:27:09Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmh
oai:ipsj.ixsq.nii.ac.jp:000771482018-03-30T07:23:32Z01164:02592:06240:06514
Complexity of Minimum Certificate Dispersal Problem with Tree StructureComplexity of Minimum Certificate Dispersal Problem with Tree Structureenghttp://id.nii.ac.jp/1001/00077148/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=77148&item_no=1&attribute_id=1&file_no=1Copyright (c) 2011 by the Information Processing Society of JapanNagoya Institute of TechnologyRitsumeikan UniversityKyushu UniversityNagoya Institute of TechnologyTaisuke, IzumiTomoko, IzumiHirotaka, OnoKoichi, WadaGiven an n-vertex graph G = (V, E) and a set R ⊆ {{x, y} | x, y ∈ V } of requests, we consider to assign a set of edges to each vertex in G so that for every request {u, v} in R the union of the edge sets assigned to u and v contains a path from u to v. The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinality of the edge set assigned to each vertex. This problem has been shown to be LOGAPX-complete for the most general setting, and APX-hard and 2-approximable in polynomial time for dense request sets, where R forms a clique. In this paper, we investigate the complexity of MCD with sparse (tree) structures. We first show that MCD is APX-hard when R is a tree, even a star. We then explore the problem from the viewpoint of the maximum degree Δ of the tree: MCD for tree request set with constant Δ is solvable in polynomial time, while that with Δ = Ω(n) is 2:56-approximable in polynomial time but hard to approximate within 1:01 unless P=NP. As for the structure of G itself, we show that the problem can be solved in polynomial time if G is a tree.Given an n-vertex graph G = (V, E) and a set R ⊆ {{x, y} | x, y ∈ V } of requests, we consider to assign a set of edges to each vertex in G so that for every request {u, v} in R the union of the edge sets assigned to u and v contains a path from u to v. The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinality of the edge set assigned to each vertex. This problem has been shown to be LOGAPX-complete for the most general setting, and APX-hard and 2-approximable in polynomial time for dense request sets, where R forms a clique. In this paper, we investigate the complexity of MCD with sparse (tree) structures. We first show that MCD is APX-hard when R is a tree, even a star. We then explore the problem from the viewpoint of the maximum degree Δ of the tree: MCD for tree request set with constant Δ is solvable in polynomial time, while that with Δ = Ω(n) is 2:56-approximable in polynomial time but hard to approximate within 1:01 unless P=NP. As for the structure of G itself, we show that the problem can be solved in polynomial time if G is a tree.AN1009593X研究報告アルゴリズム（AL）2011-AL-1363182011-08-302011-08-23