21
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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". $\endgroup$
    – vzn
    Apr 3, 2012 at 15:06
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Apr 3, 2012 at 15:20
  • $\begingroup$ @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). $\endgroup$
    – Stasys
    Apr 3, 2012 at 16:04
  • $\begingroup$ @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". $\endgroup$
    – Stasys
    Apr 3, 2012 at 16:50
  • $\begingroup$ About remark 2: when you say looking for a clique in a bipartite, do you mean a complete bipartite? $\endgroup$
    – MassimoLauria
    Apr 4, 2012 at 10:55

3 Answers 3

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – Stasys
    Apr 3, 2012 at 12:51
6
$\begingroup$

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)

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Stasys
    Apr 3, 2012 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.