Cliques in an alternate graph representation

Question

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?

Answer 1

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.

Answer 2

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