9
$\begingroup$

Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 0$.

Question: Does there exist an $s-t$ path in $G$, such that the path intersects at most $k$ triangles? (For this problem a path is said to intersect a triangle if the path contains at least one edge from the triangle.)

$\endgroup$
  • 3
    $\begingroup$ Is this wrong? We assign weight to each edge and then we find shortest st path. Weight of each edge is the number of triangles which are including that edge. The weight of this path is not equal to the number of triangles it meets but it's a s-t path with minimum number of triangles. (The possible problem is that we may count one or more triangles twice because we visit two edges of that triangle but the reason that we choose them is that they are smaller than going through the other edge of the triangle and also we have simple path means two edges of a triangle are next to each other). $\endgroup$ – Saeed Jan 29 '15 at 18:01
  • 3
    $\begingroup$ @Saeed I don't understand: what is the argument that overcounting doesn't make you choose a suboptimal path? Your algorithm is certainly a 2-approximation. Maybe a fix is to add an edge $(u, w)$ for every path $u\to v \to w$ with weight equal to the number of triangles containing both $(u,v)$ and $(v,w)$ $\endgroup$ – Sasho Nikolov Jan 29 '15 at 18:27
  • 2
    $\begingroup$ Right, we may go from u to v and then we choose x (some other node not in the triangle uvw) then we go to w which is wrong (my mistake was that I missed in between vertices which are not in the triangle uvw), but with your fix it is correct because for every st path with $\alpha$ triangles in the original graph there is a path of weight $\alpha$ in the auxiliary graph. Furthermore the weight of the path in the new graph is always at least as the number of triangles in the corresponding path in the original graph. $\endgroup$ – Saeed Jan 29 '15 at 22:37
  • 1
    $\begingroup$ I give a little bit more thought about it, even after fix it doesn't work. Sorry Andras if I brought a wrong hope. To see why fix is wrong consider vertices $u->v->w->x$ in a path $P$ and we have a triangle $u,v,w$ and $v,w,x$ and suppose edges $vx$ and $uw$ are incident to too many triangles. If we use an artificial new edge which connects $u->w$ then we counted the triangle $v,w,x$ twice. P.S: My reasoning again was wrong because I thought we simply replace $u->v$ and $v->w$ with new (multi) edge $u->w$. If we add those artificial edges for every path it will work trivially. Seems it's NPC. $\endgroup$ – Saeed Jan 30 '15 at 9:44
  • 1
    $\begingroup$ My idea won't work - I'd need to maintain multiple sets, and I think there will be too many of them. $\endgroup$ – reinierpost Jan 30 '15 at 13:55
1
$\begingroup$

Assume there are no self-edges in $G$.

For each edge between node $v_i$ and $v_j$ in $G$, let $E[i,j]=1$, and $E[i,j]=0$ if there is no edge. Compute $n\times n$ matrix $C[i,j]=\sum_{k=1}^n E[i,k]\cdot E[k,j]$, which gives the number of two-hop paths between each pair of nodes $v_i$ and $v_j$. Then for edge between $v_i$ and $v_j$ in $G$ compute $D[i,j]=E[i,j]\cdot C[i,j]$ otherwise set $D[i,j]=\infty$, which gives the number of triangles the edge is part of (or infinity if there is no edge). The matrix multiplication needed to compute $C$ costs $O(n^3)$ (could be computed faster depending on sparsity of $G$).

Now compute $n\times n$ matrix $A$, such that $A[i,j]=\min(D[i,j],\min_k(D[i,k]+D[k,j]-E[i,j]))$. $A$ is all shortest-paths in $D$ of length up to two augmented to account for paths that go along two edges of some triangle.

Now just compute the shortest path between $v_i$ and $v_j$ in $G$ on a new graph of which $A$ is the (weighted) adjacency matrix using Dijkstra (since all edge-weights are positive) i.e. and determine if $A^*[i,j]\leq k$, where $A^*$ is the closure over the tropical semiring (which gives the distance matrix).

$\endgroup$

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.