23

As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. 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 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) 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$.

a3nm
  • 9,269
  • 27
  • 86
Stasys
  • 6,765
  • 29
  • 54
  • 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 Apr 03 '12 at 15:06
  • 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 – vzn Apr 03 '12 at 15:20
  • @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 Apr 03 '12 at 16:04
  • @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 Apr 03 '12 at 16:50
  • About remark 2: when you say looking for a clique in a bipartite, do you mean a complete bipartite? – MassimoLauria Apr 04 '12 at 10:55
  • @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 Apr 04 '12 at 12:00
  • 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 – vzn Apr 21 '13 at 02:01

3 Answers3

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.

MassimoLauria
  • 1,841
  • 16
  • 21
  • 1
    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 Apr 03 '12 at 12:51
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)

user15669
  • 71
  • 1
  • 3
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 by Kilby et al

vzn
  • 11,014
  • 2
  • 31
  • 64
  • 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 Apr 03 '12 at 09:52