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