Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

EDITS: corrected $r$ to add edges just like $f$ does in paragraph 8 per the first comment below. Also specified the Clique problem of interest in paragraph 2.

Having received no response to this question on math.SE, I'm asking it here. Thanks for your help.

In the Wikipedia article on the Clique problem, we are told that under the brute-force algorithm, there are potentially exponentially many subgraphs of a given graph that must be checked as possible cliques. The particular Clique problem I'm interested in is the problem of finding a clique larger than a given size.

Informally, the question here is whether an unknown representation of graphs will also have a possibly exponential number of subgraphs that must be checked as possible cliques under the brute-force algorithm.

I'll try to make this more precise by first giving a function to build up normal graphs, and then a new, different function to build up the unknown representation with properties that the new function must satisfy. The whole discussion here is about undirected graphs.

Let's start by defining an operation that will build up a normal undirected graph. Let $E$ denote the null graph: $0$ nodes, $0$ edges. Let $f$ be the following operation:

$f(n_1, n_2, G)$

$f$ takes a graph $G$ and returns a graph with the edge from $n_1$ to $n_2$ added to $G$. So while the null graph $E$ is definable without $f$, all other standard graphs in our discussion are built by $f$: $f(n_1, n_2, G)$ where $G$ could equal $E$.

As an example, the expression $f(n_1, n_2, E)$ returns the graph $(\{n_1, n_2\}, \{(n_1, n_2)\})$.

Now consider an alternate graph representation $H$, built by a function we'll call $r$ that adds edges like $f$ does. But $H$ is an unknown representation that must obey the properties below.

First let's describe a similarity relation ($\sim$) between $G$ and $H$:

Case 1. $G \sim H$ if $G = E$ and $H = E$.
Case 2. $G \sim H$ if $G = f(n_1, n_2, G_1)$, $H = r(n_1, n_2, H_1)$, and $G_1 \sim H_1$.

As before, the null graph $E$ is definable without $r$, but all others in the unknown representation are built by $r$: $r(n_1, n_2, H)$ where $H$ could equal $E$.

The representation $H$ must obey the following properties:

  1. Just as $G$ is built by successive applications of $f$ to the null graph $E$, $H$ is built by successive applications of $r$ to the null graph $E$.
  2. The order in which the edges of a graph are added doesn't matter: in ordinary graphs, $f(n_1, n_2, f(n_3, n_4, G)) = f(n_3, n_4, f(n_1, n_2, G))$; in the unknown representation, $r(n_1, n_2, r(n_3, n_4, H)) = r(n_3, n_4, r(n_1, n_2, H))$.
  3. Since we're talking about undirected graphs, the order in which the nodes of an edge are specified doesn't matter: in ordinary graphs, $f(n_1, n_2, G) = f(n_2, n_1, G)$; in the alternate representation, $r(n_1, n_2, H) = r(n_2, n_1, H)$.
  4. Just as for $G$, $H$ has an operation $hasClique(\{n_1,...,n_k\}, H)$ which is true exactly when there is a clique among the nodes $\{n_1,...,n_k\}$.
  5. Consider a graph $G$ with nodes $\{n_1,...,n_m\}$ and a subset $\{n_i,...,n_j\}$ and $G \sim H$ for some $H$. Then we require that nodes $\{n_i,...,n_j\}$ form a clique in $G$ if and only if the nodes $\{n_i,...,n_j\}$ form a clique in $H$. What I'm trying to capture here is that $H$ has a clique wherever $G$ does and vice versa for $G \sim H$.

Question: Can we conclude that $H$ has potentially exponentially many subgraphs that must be checked as possible cliques under the brute-force algorithm, just as in normal graphs?

share|improve this question
2  
It's not clear to me what you mean by an "unknown" representation. Is it possible you could elaborate on this? In what way are these not just normal graphs? Are there any graphs that you can't construct using this method? Also, in paragraph 8, do you mean $r$ adds edges life $f$, rather than nodes? –  Luke Mathieson Nov 27 '12 at 6:20
    
@LukeMathieson: Thanks for your insightful questions and your correction regarding paragraph 8; I've incorporated it into the body of the question. As for "unknown" representation, I'm trying to reason about Turing Machines solving the Clique problem; I don't know what representations they're using, but I'm assuming we can add edges to this representation one at a time as the input is read in. As for the normal graphs question, I'm hoping that the unknown representation is as much like normal graphs as possible, including the ability to construct any graph. –  ShyPerson Nov 28 '12 at 3:35

2 Answers 2

up vote 1 down vote accepted

Like Joe, I'm assuming that you want to find all maximal cliques.

Assuming your representation can represent all graphs (and there's no reason to suspect otherwise), then there's certainly still possibly exponentially many maximal cliques as subgraph - as Joe suggested, this is a property of the graph, independent of the representation. So with the actual reporting of the cliques, we still have to potentially "say" an exponential number of things, so regardless of how tightly we can encode a graph, there's still an exponential number to report.

The question I guess is then whether by some clever representation we can reduce the number of (sub)graphs that we have to check to enumerate all the maximal cliques. In principle I guess this is possible, there's no a priori reason we couldn't decorate a data structure with additional information that would help us to enumerate cliques - the problem is then that this data structure could grow exponentially compared to the size of the original input. So in a sense it would add nothing - we're just hiding computation time in the space the data takes up.

share|improve this answer

You haven't specified exactly what your output is, but if it is the standard "output all maximal cliques", then the size of your output is exponential in the worst case, and therefore regardless of what algorithm you use, or what your representation* is, the algorithm may have to spend exponential time, just to output the answer.

*This is assuming the number of cliques you can represent in a single machine word is at most polynomial (which it clearly is, for any reasonable model).

share|improve this answer
    
I've edited the question to specify the output. –  ShyPerson Nov 28 '12 at 3:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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