We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let gamma : N -> Q(+) be any density function, i.e., gamma is computable in po...
详细信息
We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let gamma : N -> Q(+) be any density function, i.e., gamma is computable in polynomial time and satisfies gamma(k) <= k - 1 for all k is an element of N. Then gamma-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least gamma(k). For gamma(k) = k - 1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for gamma(k) = 2. We ask for the possible functions gamma such that gamma-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: gamma CLUSTER is NP-complete if gamma = 2 + Omega(1/k(1-epsilon)) for some epsilon > 0 and has a polynomial-time algorithm for gamma = 2 + O(1/k). The algorithm also shows that for Y = 2 + O(1/k(1-o(1))), gamma-CLUSTER is solvable in subexponential time 2(no(1)). (c) 2006 Elsevier B.V. All fights reserved.
We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let gamma : N -> Q(+) be any density function, i.e., gamma is computable in po...
详细信息
ISBN:
(纸本)3540401768
We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let gamma : N -> Q(+) be any density function, i.e., gamma is computable in polynomial time and satisfies gamma(k) <= k - 1 for all k is an element of N. Then gamma-CLUSTER is the problem of deciding, given an undirected graph G and a natural number k, whether there is a subgraph of G on k vertices that has average degree at least gamma(k). For gamma(k) = k - 1, this problem is the same as the well-known CLIQUE problem, and thus NP-complete. In contrast to this, the problem is known to be solvable in polynomial time for gamma(k) = 2. We ask for the possible functions gamma such that gamma-CLUSTER remains NP-complete or becomes solvable in polynomial time. We show a rather sharp boundary: gamma CLUSTER is NP-complete if gamma = 2 + Omega(1/k(1-epsilon)) for some epsilon > 0 and has a polynomial-time algorithm for gamma = 2 + O(1/k). The algorithm also shows that for Y = 2 + O(1/k(1-o(1))), gamma-CLUSTER is solvable in subexponential time 2(no(1)). (c) 2006 Elsevier B.V. All fights reserved.
暂无评论