<p>Assume there are no self-edges in $G$.</p>

<p>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$). </p>

<p>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. </p>

<p>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).</p>

CC BY-SA 3.0
2015-02-01T21:53:57.600Z
2015-02-10T12:52:18.327Z
2015-02-10T12:52:18.327Z
Edgar
<p><strong>Instance:</strong> An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 0$.</p>

<p><strong>Question:</strong> 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.)</p>

CC BY-SA 3.0
2015-01-29T18:01:40.613Z
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).
Saeed
CC BY-SA 3.0
2015-01-29T18:27:10.947Z
@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)$
Sasho Nikolov
CC BY-SA 3.0
2015-01-29T22:37:49.017Z
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.
Saeed
CC BY-SA 3.0
2015-01-30T09:44:54.267Z
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.
Saeed
CC BY-SA 3.0
2015-01-30T10:50:42.720Z
As the weight, don't assign the number of triangles, but the set of triangles itself (e.g. represented as a bit vector). The number of triangles is polynomial and so is the union operation on them. So you can just run Floyd/Dijkstra with this cost function and it will be polynomial.
reinierpost
CC BY-SA 3.0
2015-01-30T10:51:19.103Z
@reinierpost, I'm writing a complete solution right now. It's similar to what you wrote. (I hope to be correct this time)
Saeed
CC BY-SA 3.0
2015-01-30T11:24:30.543Z
@reinierpost, Just a quick note. If we assign number of triangles for every path as the number of paths are exponential then it does not work but the point is that we have a sequence not a set so we can do it a little bit more wiser e.g like using BFS, that means we looking at subsequences (which are polynomially bounded) not subsets (which are exponentially many).
Saeed
CC BY-SA 3.0
2015-01-30T13:36:59.507Z
No, that is not my idea. The idea is to use the sets as the values of the cost function in Floyd/Dijkstra's algorithm, so they represent the minimal cost between two vertices found thus far.
reinierpost
CC BY-SA 3.0
2015-01-30T13:55:02.550Z
My idea won't work - I'd need to maintain multiple sets, and I think there will be too many of them.
reinierpost
CC BY-SA 3.0
2015-01-31T10:00:25.860Z
@reinierpost I already mentioned why your idea is wrong. But still I think mine is reasonable even so my answer was not quite correct and I deleted the answer. (needs time to think about it and write it properly)
Saeed
CC BY-SA 3.0
2015-01-31T11:31:11.147Z
I now see why your solution looked the way it did. It might work.
reinierpost
<cc.complexity-theory><graph-algorithms>
Is the complexity of this path problem known?
Andras Farago
# Is the complexity of this path problem known?

(Asked by: username_0 on 2015-01-29)

**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.)

**Tags:** cc.complexity-theory, graph-algorithms

> **Comments:**
> **username_1**: 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).  
> **username_2**: @username_1 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)$  
> **username_1**: 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.  
> **username_1**: 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.  
> **username_3**: As the weight, don't assign the number of triangles, but the set of triangles itself (e.g. represented as a bit vector). The number of triangles is polynomial and so is the union operation on them. So you can just run Floyd/Dijkstra with this cost function and it will be polynomial.  
> **username_1**: @username_3, I'm writing a complete solution right now. It's similar to what you wrote. (I hope to be correct this time)  
> **username_1**: @username_3, Just a quick note. If we assign number of triangles for every path as the number of paths are exponential then it does not work but the point is that we have a sequence not a set so we can do it a little bit more wiser e.g like using BFS, that means we looking at subsequences (which are polynomially bounded) not subsets (which are exponentially many).  
> **username_3**: No, that is not my idea. The idea is to use the sets as the values of the cost function in Floyd/Dijkstra's algorithm, so they represent the minimal cost between two vertices found thus far.  
> **username_3**: My idea won't work - I'd need to maintain multiple sets, and I think there will be too many of them.  
> **username_1**: @username_3 I already mentioned why your idea is wrong. But still I think mine is reasonable even so my answer was not quite correct and I deleted the answer. (needs time to think about it and write it properly)  
> **username_3**: I now see why your solution looked the way it did. It might work.  

---

## 1 answers

### Answer by username_4 on 2015-02-01. Score: 1

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).


---

