I'm learning about $P/NP$ and my friend used an example in which he said that if you have a triangle in an undirected graph which is basically a set of three nodes in which all pairs of nodes are connected by an edge, and $TRIANGLE = \{\langle G \rangle | G$ is an undirected graph that has a triangle $\}$. He says that $TRIANGLE$ is in $P$. In other words he says $TRIANGLE \in P$. But I don't understand why.
Thanks in advance for the help!
$\endgroup$ 32 Answers
$\begingroup$Here's pseudocode for an algorithm to determine whether a graph $(V,E)$ contains a triangle:
for x in V: for y in V: for z = in V: if x and y and z are all different and {x,y} is in E and {y,z} is in E and {x,z} is in E then print "yes" and terminate print "no" and terminateThe inner loop is executed $|V|^3$ times, and even without clever data structures, checking whether some pair is in $E$ cannot take more than $O(n)$ time where $n$ is the size of the input, so the total running time is $O(n^4)$, at worst.
$\endgroup$ 1 $\begingroup$To see that $TRIANGLES$ is in P, we can construct a basic algorithm:
We can assume our graph is connected and has no multi-edges/loops. This is since if $G$ is disconnected, we just run our algorithm on each component, and multi-edges and loops don't help in finding a triangle so we can safely ignore them.
Now for every edge $uv \in E(G)$, we consider all vertices $x \in V(G)$ and see if edge $xu$ and $xv$ exist (we can do this polynomially). If they do, then we stop and conclude $G$ has a triangle. Otherwise $G$ does not have a triangle.
This algorithm runs in $O(|V(G)|*|E(G)|)$. Lets suppose $|V(G)| =n$. Since we can assume connectivity and no loops or multi-edges $|E(G)| \leq \frac{n(n-1)}{2}$.
Therefore we have $|V(G)|*|E(G)| \leq \frac{2n^2(n-1)}{2}$. Thus the algorithm runs in $O(n^{3})$ time which is polynomial in the number of vertices, and thus $TRIANGLES$ is in $P$.
I assume there is a more efficient algorithm for doing this.
$\endgroup$ 2
