<p>We did some research on the problem of <strong>proving</strong> in tree-like Resolution whether a fixed graph $G$ has a clique of size $k$ (where $k$ is usually small). In particular we discovered that refutations of size $n^{\Omega(k)}$ are needed for a large class of graphs. </p>

<p>You can find the paper <em>Parameterized Complexity of DPLL Search Procedures</em> at this <a href="http://wwwusers.di.uniroma1.it/~lauria/writings.html">link</a>.</p>

CC BY-SA 3.0
2012-04-03T12:51:46.963Z
A very nice result! Actually, my question arose when trying to show the **same** result for tree-like cutting plane (CP) refutations for the (clique) problem. For tree-like derivations we have two (only?) tools: (1) communication complexity arguments, and (2) Player-Delayer games of Pudlak and Impagliazzo. Remark 2 implies that (1) will (provably) fail for the Clique problem. Is there some analogy of (2) in the case of CP proofs?
Stasys
CC BY-SA 3.0
2012-04-03T11:54:07.583Z
2012-04-03T11:54:07.583Z
MassimoLauria
<p>I believe this paper may answer your questions: <a href="http://arxiv.org/abs/1204.6484">http://arxiv.org/abs/1204.6484</a></p>

<p>The paper defines families of NP hard 3SAT problems, such that the structure of the formula is fixed for every n, and the input is the polarity of the formula.</p>

<p>Using the standard reduction from 3SAT to CLIQUE (each 3CNF clause defines a set of 8  possible assignments (or 7 satisfying assignments), with edges between non conflicting assignments), there is a graph such that after removing one vertex for each clause, it is NP hard to find the maximal clique (or even to approximate its size, using graph products or derandomized graph products)</p>

CC BY-SA 3.0
2013-04-17T09:05:27.827Z
2013-04-17T09:05:27.827Z
user15669
<p>re Q3, there is some empirical work on the "backbone" and possible "backdoors" of SAT problems. the backbone is the set of literals that are true in every satisfying assignment. A backdoor into a SAT problem is a (hopefully small) set of variables which provide a “short cut” into solving the problem. these two structures would probably be helpful and/or key in understanding what you refer to as "sub-CNFs" or CNFs with some variables removed. but also DP, davis putnam algorithm can be seen as systematically exploring many "sub-CNFs" of the CNF to solve it.</p>

<p>[1] <a href="http://www.cse.unsw.com.au/~tw/kstwaaai05.pdf" rel="nofollow">Backbones and Backdoors in Satisfiability</a> by Kilby et al</p>

CC BY-SA 3.0
2012-04-03T09:52:17.873Z
Thanks for the reference! Indeed, these two concepts seem to be important in SAT solvers. The "backdoors" in our case correspond to sets of variables (=vertices) whose setting to 0/1 makes clique problem simple. If there is a small (logarithmic) backdoor $S$, then we have a small circuit (just by trying all assignments to $S$). But I admit that the backdoors are large for most graphs.
Stasys
CC BY-SA 3.0
2012-04-02T20:55:09.920Z
2012-04-02T20:55:09.920Z
vzn
<p>As we know, the <span class="math-container">$k$</span>-clique function <span class="math-container">$CLIQUE(n,k)$</span> takes a (<a href="https://en.wikipedia.org/wiki/Glossary_of_graph_theory" rel="nofollow noreferrer">spanning</a>) subgraph <span class="math-container">$G\subseteq K_n$</span> of a complete <span class="math-container">$n$</span>-vertex graph <span class="math-container">$K_n$</span>, and outputs <span class="math-container">$1$</span> iff <span class="math-container">$G$</span> contains a <a href="https://en.wikipedia.org/wiki/Glossary_of_graph_theory" rel="nofollow noreferrer"><span class="math-container">$k$</span>-clique</a>. Variables in this case correspond to <i>edges</i> of <span class="math-container">$K_n$</span>.
It is known (Razborov, Alon-Boppana)
that, for <span class="math-container">$3\leq k\leq n/2$</span>, this function requires monotone
circuits of size about <span class="math-container">$n^k$</span>.</p>
<p>But what if we take one <b>fixed</b> graph <span class="math-container">$G\subseteq K_n$</span>, and consider
the monotone boolean function <span class="math-container">$CLIQUE(G,k)$</span>, which takes a subset <span class="math-container">$S\subseteq [n]$</span> of vertices, and outputs <span class="math-container">$1$</span> iff some <span class="math-container">$k$</span> vertices in <span class="math-container">$S$</span> form a clique in <span class="math-container">$G$</span>. Variables in this case correspond to <i>vertices</i> of <span class="math-container">$K_n$</span>, and the function is just the standard clique function but restricted to the <a href="https://en.wikipedia.org/wiki/Glossary_of_graph_theory" rel="nofollow noreferrer"><b>spanning</b></a> subgraphs of one <b>fixed</b> graph <span class="math-container">$G$</span>.</p>
<blockquote>
<b>1.</b> Does there exist <span class="math-container">$n$</span>-vertex graphs <span class="math-container">$G$</span> for which  <span class="math-container">$CLIQUE(G,k)$</span> requires monotone
circuits of size larger than <span class="math-container">$n^{O(\log n)}$</span>? I guess - NO.
</blockquote>
<blockquote>
<b>2.</b> Is <span class="math-container">$CLIQUE(G_n,k)$</span> an NP-hard problem for some sequence of graphs 
<span class="math-container">$(G_n\colon n=1,2\ldots)$</span>? I guess - NO.
</blockquote>
<p>Note that if <span class="math-container">$C_1,\ldots,C_r$</span> are all maximal cliques in <span class="math-container">$G$</span>, then  <span class="math-container">$CLIQUE(G,k)$</span>
can be computed as an OR of <span class="math-container">$r$</span> threshold-<span class="math-container">$k$</span> functions, the <span class="math-container">$i$</span>-th of
which tests whether <span class="math-container">$|S_a\cap C_i|\geq k$</span>. Thus, if <span class="math-container">$r=poly(n)$</span>, then the entire
circuit is of polynomial size. But what about graphs with an
exponential number of maximal cliques? (A clique is maximal it no
vertex can be added to it.)</p>
<p>It is possible to &quot;embed&quot; <span class="math-container">$CLIQUE(m,k)$</span> into <span class="math-container">$CLIQUE(H,k)$</span> for a particular
graph <span class="math-container">$H$</span> on <span class="math-container">$n=2^m$</span> vertices. In particular, <a href="https://web.vu.lt/mif/s.jukna/EC_Book_2nd/full-graph.pdf" rel="nofollow noreferrer">Bollobas and Thomason (1981)</a> have shown that,
if <span class="math-container">$H$</span> is a Hadamard graph whose vertices
are subsets of <span class="math-container">$[m]$</span>, and two vertices <span class="math-container">$u$</span> and <span class="math-container">$v$</span> are adjacent iff <span class="math-container">$|u\cap v|$</span> is
even, then <span class="math-container">$H$</span> contains an isomorphic copy of every graph <span class="math-container">$G$</span> on <span class="math-container">$m$</span> vertices.
Can this fact be combined with Razborov´s lower bound (of about <span class="math-container">$m^k$</span>)
for <span class="math-container">$CLIQUE(m,k)$</span> to conclude that  <span class="math-container">$CLIQUE(H,k)$</span> requires monotone circuits
of size about <span class="math-container">$m^k$</span>?  A potential problem here is that, even though the graph <span class="math-container">$H$</span> &quot;contains&quot; <i>all</i> <span class="math-container">$m$</span>-vertex graphs, these graphs are <b>not</b> on the <b>same</b> set of vertices.
And Razborov's argument rquires that positive and negative inputs
(<span class="math-container">$k$</span>-cliques and complements of complete <span class="math-container">$(k-1)$</span>-partite graphs) are
graphs on the <b>same</b> set of vertices. Moreover, all positive inputs (<span class="math-container">$k$</span>-cliques)
are just isomorphic copies of one and the same <i>fixed</i> <span class="math-container">$k$</span>-clique.</p>
<blockquote>
<b>3.</b> Any ideas? Has anybody seen such type of problems being considered? 
I mean, decision problems for subgraphs of a <b>fixed</b> graph. Or, say, 
the SAT problem for sub-CNFs of one <b>fixed</b>
(satisfiable) CNF (obtained by removing some literals)?
</blockquote>
<b>Motivation:</b> Problems of this kind are related to the complexity of combinatorial optimization algorithms. But they seem to be interesting in themself.
Why should we seek for algorithms that are efficient on <i>all</i> graphs? In reality, we
are usually interested in the properties of small pieces of one (large) graph
(network of streets in a country, or facebook, or the like).
<p>
<b>Remark 1:</b> If the graph <span class="math-container">$G=(L\cup R,E)$</span> is <b>bipartite</b>, then the vertex-edge incidence matrix of the inequalities <span class="math-container">$x_u+x_v\leq 1$</span> for all <span class="math-container">$(u,v)\not\in E$</span> is totally unimodular, and one can solve the clique problem on induced subgraphs of <span class="math-container">$G$</span> via linear programming. Thus, for bipartite graphs <span class="math-container">$G$</span>, <span class="math-container">$CLIQUE(G,k)$</span> <b>has</b> a small (albeit  non-monotone) circuit. 
<p>
<b>Remark 2:</b> An indication, that in the case of <b>bipartite</b> graphs <span class="math-container">$G$</span>, the answer to Question 1 "should" indeed be NO is that then the following monotone Karchmer-Wigderson game on <span class="math-container">$G$</span> needs only <span class="math-container">$O(\log n)$</span> bits of communication. Let 
<span class="math-container">$k$</span> be the largest number of vertices in a complete bipartite subgraph of <span class="math-container">$G$</span>.
Alice gets a set <span class="math-container">$A$</span> of red nodes, Bob a set <span class="math-container">$B$</span> of blue nodes such that <span class="math-container">$|A|+|B|&gt;k$</span>. The goal is to find a non-edge between <span class="math-container">$A$</span> and <span class="math-container">$B$</span>.

CC BY-SA 3.0
2012-04-03T15:06:03.583Z
more thoughts (1) it seems like you might get a similar result defining a "filter" function that has same # of variables as edges and "filters" edges of the fixed graph based on 0/1 values of the boolean variables....? this might decrease the analysis somewhat due to the induced graph construction that moves from edges to vertices. (2) a key simpler question is embedded in your question which alone is worthwhile addressing. what are some graphs with exponential maximal cliques? the hadamard example may not suffice because its so "large".
vzn
CC BY-SA 3.0
2012-04-03T15:20:51.507Z
was looking into something vaguely similar recently and ran across this interesting factoid: "A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. We have recently shown that any greedy clique decomposition of a graph of order $n$ has at mostn $n^2/4$ cliques." [--mcguinness](http://www.springerlink.com/content/x752m4827540u562/)
vzn
CC BY-SA 3.0
2012-04-03T16:04:59.017Z
@vzn: To your last question. There is a simple construction (don't remember of whom). Take $n/3$ copies of vertex-disjoint "anti-trianges" (triples of vertices with no edges between them), and put edges between all vertices of any two anti-tringles. The number of maximal cliques is then $2^{n/3}$, and this is optimal (no more is possible).
Stasys
CC BY-SA 3.0
2012-04-03T16:50:39.940Z
@vzn: On McGuinness result. As I understood, he decomposes all edges into a small number of edge-disjoint maximum (size) cliques. But it may happen that the maximum clique of the **induced** subgraph does not lie in any of them. Still, the result seems to be in the "right direction".
Stasys
CC BY-SA 3.0
2012-04-04T10:55:48.470Z
About **remark 2**: when you say looking for a clique in a bipartite, do you mean a complete bipartite?
MassimoLauria
CC BY-SA 3.0
2012-04-04T12:00:33.540Z
@Massimo: Yes (sorry for being not precise). My protocol uses monotone formulas for threshold functions. A negative answer to my Q1 would give a protocol also for *non-bipartite* graphs with $O(\log^2 n)$ bits of communication. So far, I can only show that this number of bits is enough for all graphs of chromatic number $O(\log n)$. P.S. The number of max cliques in that example (replaying to "vzn") is $3^{n/3}$, not $2^{n/3}$, and no graph can have much more such cliques.
Stasys
CC BY-SA 3.0
2013-04-21T02:01:00.613Z
this question is basically looking for ways of generalizing or re-applying Razborovs proof method for monotone circuits in a novel way. for other ideas/further discussion on generalizing Razborovs monotone circuit proof method, plz respond on [monotone circuits chat room](http://chat.stackexchange.com/rooms/6870/monotone-circuits)
vzn
<cc.complexity-theory><optimization><circuit-complexity>
Clique problem on fixed graphs
Stasys
# Clique problem on fixed graphs

(Asked by: username_0 on 2012-04-02)

As we know, the $k$-clique function $CLIQUE(n,k)$ takes a ([spanning](https://en.wikipedia.org/wiki/Glossary_of_graph_theory)) subgraph $G\subseteq K\_n$ of a complete $n$-vertex graph $K\_n$, and outputs $1$ iff $G$ contains a [$k$-clique](https://en.wikipedia.org/wiki/Glossary_of_graph_theory). Variables in this case correspond to *edges* of $K\_n$.
It is known (Razborov, Alon-Boppana)
that, for $3\leq k\leq n/2$, this function requires monotone
circuits of size about $n^k$.

But what if we take one **fixed** graph $G\subseteq K\_n$, and consider
the monotone boolean function $CLIQUE(G,k)$, which takes a subset $S\subseteq [n]$ of vertices, and outputs $1$ iff some $k$ vertices in $S$ form a clique in $G$. Variables in this case correspond to *vertices* of $K\_n$, and the function is just the standard clique function but restricted to the [**spanning**](https://en.wikipedia.org/wiki/Glossary_of_graph_theory) subgraphs of one **fixed** graph $G$.

> **1.** Does there exist $n$-vertex graphs $G$ for which $CLIQUE(G,k)$ requires monotone
> circuits of size larger than $n^{O(\log n)}$? I guess - NO.

> **2.** Is $CLIQUE(G\_n,k)$ an NP-hard problem for some sequence of graphs
> $(G\_n\colon n=1,2\ldots)$? I guess - NO.

Note that if $C\_1,\ldots,C\_r$ are all maximal cliques in $G$, then $CLIQUE(G,k)$
can be computed as an OR of $r$ threshold-$k$ functions, the $i$-th of
which tests whether $|S\_a\cap C\_i|\geq k$. Thus, if $r=poly(n)$, then the entire
circuit is of polynomial size. But what about graphs with an
exponential number of maximal cliques? (A clique is maximal it no
vertex can be added to it.)

It is possible to "embed" $CLIQUE(m,k)$ into $CLIQUE(H,k)$ for a particular
graph $H$ on $n=2^m$ vertices. In particular, [Bollobas and Thomason (1981)](https://web.vu.lt/mif/s.jukna/EC_Book_2nd/full-graph.pdf) have shown that,
if $H$ is a Hadamard graph whose vertices
are subsets of $[m]$, and two vertices $u$ and $v$ are adjacent iff $|u\cap v|$ is
even, then $H$ contains an isomorphic copy of every graph $G$ on $m$ vertices.
Can this fact be combined with Razborov´s lower bound (of about $m^k$)
for $CLIQUE(m,k)$ to conclude that $CLIQUE(H,k)$ requires monotone circuits
of size about $m^k$? A potential problem here is that, even though the graph $H$ "contains" *all* $m$-vertex graphs, these graphs are **not** on the **same** set of vertices.
And Razborov's argument rquires that positive and negative inputs
($k$-cliques and complements of complete $(k-1)$-partite graphs) are
graphs on the **same** set of vertices. Moreover, all positive inputs ($k$-cliques)
are just isomorphic copies of one and the same *fixed* $k$-clique.

> **3.** Any ideas? Has anybody seen such type of problems being considered?
> I mean, decision problems for subgraphs of a **fixed** graph. Or, say,
> the SAT problem for sub-CNFs of one **fixed**
> (satisfiable) CNF (obtained by removing some literals)?

**Motivation:** Problems of this kind are related to the complexity of combinatorial optimization algorithms. But they seem to be interesting in themself.
Why should we seek for algorithms that are efficient on *all* graphs? In reality, we
are usually interested in the properties of small pieces of one (large) graph
(network of streets in a country, or facebook, or the like).

**Remark 1:** If the graph $G=(L\cup R,E)$ is **bipartite**, then the vertex-edge incidence matrix of the inequalities $x\_u+x\_v\leq 1$ for all $(u,v)\not\in E$ is totally unimodular, and one can solve the clique problem on induced subgraphs of $G$ via linear programming. Thus, for bipartite graphs $G$, $CLIQUE(G,k)$ **has** a small (albeit non-monotone) circuit.

**Remark 2:** An indication, that in the case of **bipartite** graphs $G$, the answer to Question 1 "should" indeed be NO is that then the following monotone Karchmer-Wigderson game on $G$ needs only $O(\log n)$ bits of communication. Let
$k$ be the largest number of vertices in a complete bipartite subgraph of $G$.
Alice gets a set $A$ of red nodes, Bob a set $B$ of blue nodes such that $|A|+|B|>k$. The goal is to find a non-edge between $A$ and $B$.

**Tags:** cc.complexity-theory, optimization, circuit-complexity

> **Comments:**
> **username_1**: more thoughts (1) it seems like you might get a similar result defining a "filter" function that has same # of variables as edges and "filters" edges of the fixed graph based on 0/1 values of the boolean variables....? this might decrease the analysis somewhat due to the induced graph construction that moves from edges to vertices. (2) a key simpler question is embedded in your question which alone is worthwhile addressing. what are some graphs with exponential maximal cliques? the hadamard example may not suffice because its so "large".  
> **username_1**: was looking into something vaguely similar recently and ran across this interesting factoid: "A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. We have recently shown that any greedy clique decomposition of a graph of order $n$ has at mostn $n^2/4$ cliques." [--mcguinness](http://www.springerlink.com/content/x752m4827540u562/)  
> **username_0**: @username_1: To your last question. There is a simple construction (don't remember of whom). Take $n/3$ copies of vertex-disjoint "anti-trianges" (triples of vertices with no edges between them), and put edges between all vertices of any two anti-tringles. The number of maximal cliques is then $2^{n/3}$, and this is optimal (no more is possible).  
> **username_0**: @username_1: On McGuinness result. As I understood, he decomposes all edges into a small number of edge-disjoint maximum (size) cliques. But it may happen that the maximum clique of the **induced** subgraph does not lie in any of them. Still, the result seems to be in the "right direction".  
> **username_2**: About **remark 2**: when you say looking for a clique in a bipartite, do you mean a complete bipartite?  
> **username_0**: @Massimo: Yes (sorry for being not precise). My protocol uses monotone formulas for threshold functions. A negative answer to my Q1 would give a protocol also for *non-bipartite* graphs with $O(\log^2 n)$ bits of communication. So far, I can only show that this number of bits is enough for all graphs of chromatic number $O(\log n)$. P.S. The number of max cliques in that example (replaying to "username_1") is $3^{n/3}$, not $2^{n/3}$, and no graph can have much more such cliques.  
> **username_1**: this question is basically looking for ways of generalizing or re-applying Razborovs proof method for monotone circuits in a novel way. for other ideas/further discussion on generalizing Razborovs monotone circuit proof method, plz respond on [monotone circuits chat room](http://chat.stackexchange.com/rooms/6870/monotone-circuits)  

---

## 3 answers

### Answer by username_2 on 2012-04-03. Score: 11

We did some research on the problem of **proving** in tree-like Resolution whether a fixed graph $G$ has a clique of size $k$ (where $k$ is usually small). In particular we discovered that refutations of size $n^{\Omega(k)}$ are needed for a large class of graphs.

You can find the paper *Parameterized Complexity of DPLL Search Procedures* at this [link](http://wwwusers.di.uniroma1.it/~lauria/writings.html).

> **Comments:**
> **username_0**: A very nice result! Actually, my question arose when trying to show the **same** result for tree-like cutting plane (CP) refutations for the (clique) problem. For tree-like derivations we have two (only?) tools: (1) communication complexity arguments, and (2) Player-Delayer games of Pudlak and Impagliazzo. Remark 2 implies that (1) will (provably) fail for the Clique problem. Is there some analogy of (2) in the case of CP proofs?  

---

### Answer by username_3 on 2013-04-17. Score: 7

I believe this paper may answer your questions: <http://arxiv.org/abs/1204.6484>

The paper defines families of NP hard 3SAT problems, such that the structure of the formula is fixed for every n, and the input is the polarity of the formula.

Using the standard reduction from 3SAT to CLIQUE (each 3CNF clause defines a set of 8 possible assignments (or 7 satisfying assignments), with edges between non conflicting assignments), there is a graph such that after removing one vertex for each clause, it is NP hard to find the maximal clique (or even to approximate its size, using graph products or derandomized graph products)


---

### Answer by username_1 on 2012-04-02. Score: 2

re Q3, there is some empirical work on the "backbone" and possible "backdoors" of SAT problems. the backbone is the set of literals that are true in every satisfying assignment. A backdoor into a SAT problem is a (hopefully small) set of variables which provide a “short cut” into solving the problem. these two structures would probably be helpful and/or key in understanding what you refer to as "sub-CNFs" or CNFs with some variables removed. but also DP, davis putnam algorithm can be seen as systematically exploring many "sub-CNFs" of the CNF to solve it.

[1] [Backbones and Backdoors in Satisfiability](http://www.cse.unsw.com.au/~tw/kstwaaai05.pdf) by Kilby et al

> **Comments:**
> **username_0**: Thanks for the reference! Indeed, these two concepts seem to be important in SAT solvers. The "backdoors" in our case correspond to sets of variables (=vertices) whose setting to 0/1 makes clique problem simple. If there is a small (logarithmic) backdoor $S$, then we have a small circuit (just by trying all assignments to $S$). But I admit that the backdoors are large for most graphs.  

---

