# Cliques in an alternate graph representation

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?

• 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