0
$\begingroup$

I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?)

The general clique problem is defined as

$\text{CLIQUE} = \left\{ (G, k) | G = (V, E) \in \mathcal{G} \land \exists V_c \subseteq V . |V_c| \geqslant k \land V_c \text{ is clique in } G \right\}$

A clique of a given size can be found in polynomial time, for instance by this code:

# Iterates over all nodes. If node has at least size -1 neighbours,
# compares neighbour's neighbours with neighbours.
def CLIQUE(graph, size):

    for node in graph.nodes:
        if degree(graph, node) >= size - 1:         
            neighbours = graph.edges[node]
            intersection = neighbours.union(set(node))
            for neighbour in neighbours:
                print neighbour
                print graph.edges[neighbour].union(neighbour)
        intersection = intersection.intersection(graph.edges[neighbour].union(neighbour))
            print intersection
            if len(intersection) >= size:
                return True
    return False

(rest of the program)

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = dict()

    def from_file(self, deffile):
        with open(deffile, 'r') as f:
            for line in f:
                n1, n2 = line.split()
                self.nodes.add(n1)
                self.nodes.add(n2)
                if n1 in self.edges:
                    self.edges[n1].add(n2)
                else:
                    self.edges[n1] = set(n2)
                if n2 not in self.edges:
                    self.edges[n2] = set()


def degree(graph, node):

    return len(graph.edges[node])

So, given that the clique problem is 'Is there q clique of at least size k in G' and the above code returns true once it finds a clique of (at least) k nodes and runs in $\mathcal{O}(n^2)$, as it compares every node with every other node in the worst case, I don't understand how that code does not do what the general clique problem does... because apparenrtly it does not, as it runs in polynomial time and the general clique problem does not.

$\endgroup$
  • $\begingroup$ Where did you come up with the $k$-clique algorithm? I'm pretty sure it's wrong, as finding a clique of size exactly $k$ is also known to be NP-complete. $\endgroup$ – jmite Jun 27 '16 at 17:15
  • 4
    $\begingroup$ could be, I made it up on the fly, but in the other threads they say clique k were solvable in polynomial time (cs.stackexchange.com/questions/6847/…) $\endgroup$ – lo tolmencre Jun 27 '16 at 17:18
  • $\begingroup$ The reason that it's possible to find fixed-sized cliques in polynomial time is covered in the question you ask about. The reason that your pseudocode doesn't find $k$-cliques in polynomial time when $k$ is part of the input is that it doesn't work: you can't find cliques greedily but, rather, you have to backtrack. $\endgroup$ – David Richerby Jun 27 '16 at 17:40
4
$\begingroup$

It's a matter of logical quantifiers.

Consider this statement: "if every natural number $n$ is bounded above by a constant $c$, how come there is no constant $c$ that bounds every natural number $n$ by above?".

The above is an example where $\forall n.\ \exists c.\ \ldots$ does not imply $\exists c.\ \forall n.\ \ldots$. Indeed, in the former, we can choose $c$ after we see $n$, while in the latter we must do before, and we are unable to do that: whatever $c$ we choose, the statement becomes false for e.g. $n=c+1$.

To decide CLIQUE, once we take the instance $(G,k)$ to be checked, we can use an algorithm which runs on $O(n^c)$ for some $c$ -- but here we are choosing $c$ after we have seen $k$. This does not prove that CLIQUE is in P. For that, we would need to find a constant $c$, and an associated $O(n^c)$ algorithm, which would decide any instance $(G,k)$, whatever $k$ is. And this is much harder.

$\endgroup$
  • $\begingroup$ I don't quite understand. Surely the most steps needed is to compare every node with every other node, or is it not? That would be $n^2$ in the worst case. If you have a fully connected graph of $n$ nodes and are looking for a clique of size $n$ as well, then you have to compare every node with every other node. How could it get worse? And if the worst case has $n^2$ steps to solve, where does it play a role whether I know my $k$ beforehand or not? $\endgroup$ – lo tolmencre Jun 27 '16 at 17:42
  • 3
    $\begingroup$ Say you have $2k$ nodes and you need to check whether there is a clique of $k$ nodes. The naive algorithm would 1) scan all combinations of $k$ nodes chosen among the $2k$, and 2) check if that is really a clique. The part 2) is indeed $O(k^2)$, but part 1) generates an exponential number of subsets, so the total cost is exponential * quadratic which is not polynomial. $\endgroup$ – chi Jun 27 '16 at 18:20

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.