I was going over this paper and I don't understand a certain proof (section five phase 2).

Given a graph G=(V,E) partitioned into the sets of vertices L and H. The vertices in L are at most D where D is an arbitrary number and the rest of the vertices are in H.

If we take a closer look at Phase 2 (Theorem 5). For each vertex x in L compute the square of the adjacency matrix of G[N(x)] to decide whether G[N(x)] contains a triangle.

We know that the fastest way to find a triangle in a graph is using fast matrix multiplication algorithm which is $O(n^\alpha)$. So, we can define a running time of $\sum_{x \epsilon L}^{ } d(x)^\alpha$. Since we know that |L| can be at most e (number of edges) if we choose a bad D and d(x) is at most D, why Phase 2 can be done in $O(D^{\alpha-1}e)$. I was under the impression that it was $O(D^{\alpha}e)$ i.e. where is the $\alpha-1$ coming from? I'm pretty sure it's trivial, but I'm missing the point.

  • 1
    $\begingroup$ This is a basic mathematic problem. If $x_1\ge x_2\ldots \ge x_n$ then $\Sigma x_i^\alpha \le x_1^{\alpha -1}\Sigma x_i$ for $\alpha \ge 1$. $\endgroup$ – Saeed May 27 '15 at 9:38

The sum of all degrees $d(x)$ in a graph is at most $2e$. The sum of all $d(x)^{\alpha}$ is at most $(max degree)^{\alpha -1}$ times sum of all $d(x)$. Together these give the upper bound.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.