6
As suggested by the comments (thanks!), the answer is positive and rather easy.
We want to compute the pagerank of all vertices of a DAG (Directed Acyclic Graph) $G = (V,E)$ with $n$ vertices and $m$ edges. For any vertex $u$, let us denote by $d^+(u)$ its out-degree: $d^+(u) = |\{v, (u,v)\in E\}|$.
Pagerank is basically defined as the stationnary ...
5
Yes, there are many such algorithms. Two of the easiest are
(1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each tree to a supervertex, and repeat. But modify it so that after the collapse you return to a simple graph rather than a multigraph. To do so, use radix sort to sort ...
3
Found the following paper "NP-completeness of some problems of partitioning and covering in graphs" by B.Péroche.
The paper proves that deciding whether the edges of a graph can be partitioned into two simple paths is NP-Complete. I haven't looked at the reduction but it may also prove that finding the min number of paths may be hard to approximate ...
3
These are not directly comparable:
Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual approximation ratio.
The paper mentioned in the question and related work: find a cut in any graph G [of some graph family] that contains at least X fraction of ...
Only top voted, non community-wiki answers of a minimum length are eligible