Why is triangle $\in P$ (P/NP)

2.3k Views Asked by At

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!

2

There are 2 best solutions below

1
On

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 terminate

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

2
On

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.