Halldòrsson, Magnüs M. ; Kortsarz, Guy ; Radhakrishnan, Jaikumar ; Sivasubramanian, Sivaramakrishnan
(2007)
*Complete partitions of graphs*
Combinatorica, 27
(5).
pp. 519-550.
ISSN 0209-9683

Full text not available from this repository.

Official URL: http://www.springerlink.com/content/hr16318926p44p...

Related URL: http://dx.doi.org/10.1007/s00493-007-2169-9

## Abstract

A complete partition of a graph G is a partition of its vertex set in which any two distinct classes are connected by an edge. Let cp(G) denote the maximum number of classes in a complete partition of G. This measure was defined in 1969 by Gupta [19], and is known to be NP-hard to compute for several classes of graphs. We obtain essentially tight lower and upper bounds on the approximability of this problem. We show that there is a randomized polynomial-time algorithm that given a graph G with n vertices, produces a complete partition of size Ω(cp(G)/√lgn). This algorithm can be derandomized. We show that the upper bound is essentially tight: there is a constant C > 1, such that if there is a randomized polynomial-time algorithm that for all large n, when given a graph G with n vertices produces a complete partition into at least C·cp(G)/√lgn classes, then NP ⊆ RTime (n ^{O(lg lg n)}). The problem of finding a complete partition of a graph is thus the first natural problem whose approximation threshold has been determined to be of the form θ((lgn)^{c}) for some constant c strictly between 0 and 1.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Springer. |

ID Code: | 57654 |

Deposited On: | 29 Aug 2011 08:37 |

Last Modified: | 29 Aug 2011 08:37 |

Repository Staff Only: item control page