0
$\begingroup$

My question expands on a related question on the link, Why is the clique problem NP-complete? In that post the author argued that while the $k$-clique problem is NP-complete; for a fixed $k$ the $k$-clique problem is polynomial time solvable. The question "Prove that the presence of 3-clique in a graph can be decided in polynomial time" also appears in the book, S. K. Basu, "Design Method and Analysis of Algorithms, PHI, 2005, pg159.

To avoid any confusion, I felt it important to clarify that this would only be possible if the graph $G=(V,E)$ ($V$ is the set of vertices and $E$ is the set of edges) is fixed. In such a case a polynomial number of steps $R^m,$ (where $R=f(V,E)$, i.e. $R$ is a constant given by some function of vertices and edges) can be used to find the solution of 3-clique for example. So the conclusion that finding 3-clique for a fixed graph has polynomial time complexity works perfectly fine until this point.

But such a polynomial time algorithm with time complexity less than or equal to linear time complexity can not be designed to find 3-clique, i.e. $m>1$. Assuming that $k$ is fixed but $G$ is not fixed, in that case the complexity of finding 3-clique will then be exponential, unless someone can provide a polynomial time algorithm with complexity $R^m$, where $m\leq 1$ to find 3-clique for a fixed arbitrary graph. Since we are unable to prove that a polynomial time algorithm does not exist for 3-clique problem on an arbitrary graph, the computational complexity of the problem will hence be treated as being NP-complete based on the relationship $3SAT\leq_p k$-clique, a proof of which can be found in many standard books on algorithms.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What is your actual question? Also, why is $R^{2}$ exponential time? To find a 3-clique, we just need to check all sets of 3 vertices, which takes $O(n^{3})$ time, certainly polynomial in $n$ - the graph is in no way fixed. $\endgroup$
    – Luke Mathieson
    Commented Apr 9, 2015 at 5:59
  • $\begingroup$ I am not exactly posting a question, just disagreeing with an earlier answer and looking for feedback. If we are going to check all sets of 3 vertices in a graph with $n$ vertices, that means we need to consider $C^n_3$ possibilities, which will increases factorial with $n$ and not polynomially. $\endgroup$
    – jcod0
    Commented Apr 9, 2015 at 6:27
  • 3
    $\begingroup$ On the contrary, $\binom{n}{3} = O(n^3)$ is polynomial. $\endgroup$
    – Yuval Filmus
    Commented Apr 9, 2015 at 6:28
  • $\begingroup$ Is there a proof which shows that $C^n_3=O(n^3)$, if we are going to check all the $C^n_3$ possibilities which increases factorial with $n$ then how can the time complexity using big O notation be polynomial? $\endgroup$
    – jcod0
    Commented Apr 9, 2015 at 6:54
  • 3
    $\begingroup$ Welcome to CS Stack Exchange but please note that this is a question and answer site, not a discussion board. $\binom{n}{3}=\tfrac16n(n-1)(n-2)=O(n^3)$. $\endgroup$
    – David Richerby
    Commented Apr 9, 2015 at 8:17

2 Answers 2

Reset to default
2
$\begingroup$

A polynomial algorithm does exist for finding whether a graph contains a triangle. For one, you can go over all triplets $x,y,z$ of vertices, and check if the graph contains the triangle $\{x,y\},\{y,z\},\{x,z\}$. This algorithm takes $O(n^3)$. Surprisingly, there is a faster algorithm: take the adjacency matrix $A$ of the graph, and compute the trace of the matrix $A^3$. The graph contains a triangle iff the trace is positive. This algorithm takes $O(n^\omega)$, where $\omega < 2.373$ is the exponent of matrix multiplication.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Would you like to clarify the notation $n$ used in your answer. $\endgroup$
    – jcod0
    Commented Apr 9, 2015 at 6:29
  • $\begingroup$ @jcod0 When dealing with graphs, it is common to use $n$ to denote the number of vertices. This is what happens here as well. $\endgroup$
    – Juho
    Commented Apr 9, 2015 at 6:30
  • $\begingroup$ Here $n$ is the number of vertices. Most reasonable encodings of graphs take $\Omega(n)$ bits. $\endgroup$
    – Yuval Filmus
    Commented Apr 9, 2015 at 6:30
  • $\begingroup$ You're right that when we say "polynomial time", the time needs to grow polynomially in terms on the input size. Since, as I mentioned, the input size is at least $n$, this means that any $O(n^k)$ algorithm (for fixed $k$) is a polynomial time algorithm. $\endgroup$
    – Yuval Filmus
    Commented Apr 9, 2015 at 6:31
  • $\begingroup$ Thank you Yuval for the clarification. So does it mean that packing problems such as $k$-independent set (IS) is also polynomial time solveable for fixed $k$, because unlike the $k$-clique problem, in $k$-IS problem, we also need to take into consideration conflicts (i.e. two vertices with a common edge can not be selected)? $\endgroup$
    – jcod0
    Commented Apr 9, 2015 at 11:10
1
$\begingroup$

I'll try to explain how I understand this. May be after that I'll understand it better :)

"k-Clique problem" is NP-complete, and "k-Clique problem for a fixed k" is easily solvable in polynomial time, and there is no contradiction here.

Let F be a function "size of the problem" -> "time required to solve it".

"size of the problem" here is a length of an input string, which describes the problem. I guess it's not an obvious thing. It depends on "encoding". If we have a graph with $n$ vertices, we will need at least $log(n)$ characters to encode a single node id, there may be about $n*n$ edges, so we need ~ $n*n*log(n)$ characters to describe all the edges. To fully describe the problem we also need to include the "k" in the input string, so that the machine would know what kind of clique it is looking for. Probably some additional "formatting" characters would be necessary to delimit.

May be there are a little more compact ways to construct an input string. But looks like "size of the problem" is $O(n^l)$ for some $l$. I am not ready to prove it.

If $k$ is fixed, it's easy to construct a Turing machine which checks if k-Clique exists in a given graph. This machine would require polynomial time to solve the problem. Either $O(n^m)$ or $O($"size of the problem"$^m)$ - it does not really matter since "size of the problem" is $O(n^l)$.

But if $k$ is not fixed, there is no way to construct a Turing machine which would solve the problem in $O($"size of the problem"$^m)$ time. Size of the problem "is there a $n$-Clique in $2*n$ nodes graph" is polynomial of $n$, but all the techniques we used to solve the problem for a fixed $k$ would not help us to solve this problem fast (in polynomial of $n$ or polynomial of "size of the problem" time).

Improve this answer
$\endgroup$
1
  • $\begingroup$ We don't know that Clique cannot be solved in polynomial time. It's just a conjecture. $\endgroup$
    – Yuval Filmus
    Commented Apr 9, 2015 at 14:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.