Bounded Degree Closest k-Tree Power Is NP-Complete
An undirected graph G=(V, E) is the k-power of an undirected tree T=(V, E) if (u, v) ∈ E iff u and v are connected by a path of length at most k in T. The tree T is called the tree root of G. Tree powers can be recognized in polynomial time. The thus naturally arising question is whether a graph G can be modified by adding or deleting a specified number of edges such that G becomes a tree power. This problem becomes NP-complete for k≥2.Strengthening this result, we answer the main open question of Tsukiji and Chen COCOON 2004 by showing that the problem remains NP-complete when additionally demanding that the tree roots must have bounded degree.
Michael Dom Jiong Guo Rolf Niedermeier
Institut fur Informatik, Friedrich-Schiller-Universitat Jena Ernst-Abbe-Platz 2, D-07743 Jena, Fed. Rep. of Germany
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
757-766
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）