Loading...
Please wait, while we are loading the content...
Similar Documents
On Counting Cliques, Clique-covers and Independent sets in Random Graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Dixit, Kashyap Fürer, Martin |
| Copyright Year | 2018 |
| Abstract | We study the problem of counting the number of isomorphic copies of a given template graph, say H , in the input base graph, say G. In general, it is believed that polynomial time algorithms that solve this problem exactly are unlikely to exist. So, a lot of work has gone into designing efficient approximation schemes, especially, when H is a perfect matching. In this work, we present efficient approximation schemes to count k-Cliques, k-Independent sets and k-Clique covers in random graphs. We present fully polynomial time randomized approximation schemes (fpras) to count k-Cliques and k-Independent sets in a random graph on n vertices when k is at most (1 + o(1)) log n, and k-Clique covers when k is a constant. The problem of counting k-cliques and k-independent sets was an open problem in [Frieze and McDiarmid, 1997]. In other words, we have a fpras to evaluate the first (1 + o(1)) log n terms of the clique polynomial and the independent set polynomial of a random graph. [Grimmett and McDiarmid, 1975] present a simple greedy algorithm that detects a clique (independent set) of size (1 + o(1)) log2 n in G ∈ G(n, 1 2 ) with high probability. No algorithm is known to detect a clique or an independent set of larger size with non-vanishing probability. Furthermore, [Coja-Oghlan and Efthymiou, 2011] present some evidence that one cannot hope to easily improve a similar, almost 40 years old bound for sparse random graphs. Therefore, our results are unlikely to be easily improved. We use a novel approach to obtain a recurrence corresponding to the variance of each estimator. Then we upper bound the variance using the corresponding recurrence. This leads us to obtain a polynomial upper bound on the critical ratio. As an aside, we also obtain an alternate derivation of the closed form expression for the k-th moment of a binomial random variable using our techniques. The previous derivation [Knoblauch (2008)] was based on the moment generating function of a binomial random variable. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://export.arxiv.org/pdf/1411.6673 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
