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 know (Razborov, Alon-Boppana)that, for $3\leq k\leq n/2$, this function requires monotonecircuits of size about $n^k$.But what if we take one fixed graph $G\subseteq K_n$, and considerthe 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 monotonecircuits 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 ofwhich tests whether $|S_a\cap C_i|\geq k$. Thus, if $r=poly(n)$, then the entirecircuit is of polynomial size. But what about graphs with anexponential number of maximal cliques? (A clique is maximal it novertex can be added to it.)It is possible to embed $CLIQUE(m,k)$ into $CLIQUE(H,k)$ for a particulargraph $H$ on $n=2^m$ vertices. In particular, Bollobas and Thomason (1981) have shown that,if $H$ is a Hadamard graph whose verticesare subsets of $[m]$, and two vertices $u$ and $v$ are adjacent iff $|u\cap v|$ iseven, then $H$ contains an isomorphic copy of every graph $G$ on $m$ vertices.Can this fact be combined with Razborovs lower bound (of about $m^k$)for $CLIQUE(m,k)$ to conclude that  $CLIQUE(H,k)$ requires monotone circuitsof 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) aregraphs 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, weare 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$.
Clique problem on fixed graphs
cc.complexity theory;optimization;circuit complexity