✦ LIBER ✦

General Partitioning on Random Graphs

✍ Scribed by C.R. Subramanian; C.E. Veni Madhavan

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 158 KB
Volume: 42
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2001.1197

No coin nor oath required. For personal study only.

✦ Synopsis

Consider the general partitioning (GP) problem defined as follows: Partition the vertices of a graph into k parts W 1 W k satisfying a polynomial time verifiable property. In particular, consider properties (introduced by T. Feder, P. Hell, S. Klein, and R. Motwani, in "Proceedings of the Annual ACM Symposium on Theory of Computing (STOC '99), 1999" and) specified by a pattern of requirements as to which W i forms a sparse or dense subgraph and which pairs W i , W j form a sparse or dense or an arbitrary (no restriction) bipartite subgraph. The sparsity or density is specified by upper or lower bounds on the edge density d ∈ 0 1 , which is the fraction of actual edges present to the maximum number of edges allowed. This problem is NP-hard even for some fixed patterns and includes as special cases well-known NP-hard problems like k-coloring (each d W i = 0; each d W i W j is arbitrary), bisection (k = 2; W 1 = W 2 ; d W 1 W 2 ≤ b), and also other problems like finding a clique/independent set of specified size. We show that GP is solvable in polynomial time almost surely over random instances with a planted partition of desired type, for several types of pattern requirement. The algorithm is based on the approach of growing BFS trees outlined by C. R. Subramanian (in "Proceedings of the 8th Annual European Symposium on Algorithms (ESA '00), 2000," pp. 415-426).

📜 SIMILAR VOLUMES

Random walks on random simple graphs

✍ Martin Hildebrand 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 676 KB

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (logn)", where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou

On triangle-free random graphs

✍ Tomasz Łuczak 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 3 views

We show that for every k ≥ 1 and δ > 0 there exists a constant c > 0 such that, with probability tending to 1 as n → ∞, a graph chosen uniformly at random among all triangle-free graphs with n vertices and M ≥ cn 3/2 edges can be made bipartite by deleting δM edges. As an immediate consequence of th

Algorithms for graph partitioning on the

Algorithms for graph partitioning on the planted partition model

✍ Anne Condon; Richard M. Karp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 1 views

On-Line Coloring of Sparse Random Graphs

On-Line Coloring of Sparse Random Graphs and Random Trees

✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 164 KB

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random gr

Random graphs generated by the Star 2-Pr

Random graphs generated by the Star 2-Process

✍ Hanna Robalewska 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

The star 2-process ''greedily'' generates graphs with maximum degree 2 in a natural way. We can obtain information about the final graph of this process; for instance, that is almost surely 2-regular. We also find the probability of hamiltonicity and Poisson approximations of the distributions of nu

Cataloging graphs by generating them uni

Cataloging graphs by generating them uniformly at random

✍ A. Kerber; R. Laue; R. Hager; W. Weber 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB

## Abstract We describe an algorithm for cataloging graphs by generating them uniformly at random. The method used is based on a recent algorithm by Dixon and Wilf that generates orbit representatives uniformly at random. The approach is refined to graphs with prescribed numbers of edges and vertic