<p>Let $F$ be a random k-CNF formula with $n$ variables and $m$ clauses. Let $G$ be the undirected graph built in the following manner: there is a vertex $v$ for every clause $c \in F$, and there is an edge $e = (v, u)$ if and only if the clause corresponding to $v$ has at least one variable in common with the clause corresponding to $u$.</p>

<p>The question is: how many variables, on average, shall I remove from $F$ before $G$ gets divided into 2 or more connected components? Is such number of variables related to $r = \frac{m}{n}$?</p>

<p>Here is what I mean by "removing  a variable $v$ from a formula $F$": every clause $c$ in which $v$ is mentioned (no matter if positive or negative) gets shortened; if $c$ becomes empty, then it is removed from $F$.</p>

CC BY-SA 2.5
2011-03-10T17:32:44.577Z
Closed at request of original poster.
Dave Clarke
CC BY-SA 2.5
2010-09-21T09:21:52.610Z
Thanks, I'll reword the question. Jukka, did you see the last answer to my question "Monotone-2SAT and Vertex Cover"?
Giorgio Camerani
CC BY-SA 2.5
2010-09-21T09:33:02.910Z
$G'$ does not seem to add anything to your setup, as it is simply a forest of cliques.  You seem to be asking about the average connectivity of $G$, but what is the distribution of functions?
András Salamon
CC BY-SA 2.5
2010-09-21T09:57:03.657Z
I think you're right in saying that $G'$ doesn't add any value. Maybe I'll remove it from the question. Concerning your question, I forgot to say that the k-CNF formulas are random.
Giorgio Camerani
CC BY-SA 2.5
2010-09-21T10:49:24.703Z
Are the k-CNF formulas chosen uniformly at random from among the ones with m clauses and n variables?
András Salamon
CC BY-SA 2.5
2010-09-21T11:48:10.450Z
@Andras: Yes, they are.
Giorgio Camerani
CC BY-SA 2.5
2010-09-21T12:17:14.557Z
1. As András commented, the minimum number of vertices you have to remove to make a graph disconnected plus 1 is called the [(vertex) connectivity](http://en.wikipedia.org/wiki/K-vertex-connected_graph) of the graph.  If this is what you are interested in, adding this term may help reader to understand the question better.  2. You may want to add a reformulated version of the question without referring to CNF formulas because the negation does not play any role in the question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-21T13:27:40.117Z
@Tsuyoshi: $G$'s vertices correspond to $F$'s clauses: if I remove a vertex from $G$ it means I'm removing a clause from $F$. But I'm interested in removing variables of $F$, not clauses. Anyhow I feel that what Andras said is in some way related to what I'm asking. In other words: given a formula $F$, how many variables shall I remove (and which ones) in order that $F$ gets divided into 2 or more disjoint sub-formulas? Here "disjoint" means that the sub-formulas do not share any variable. @Andras: I don't see your comment any longer.
Giorgio Camerani
CC BY-SA 2.5
2010-09-21T13:36:36.847Z
Oops, you are right.  The item 1 in my previous comment was wrong.  I realized that I did not understand the problem; what do you mean by removing a variable from a CNF formula?  More specifically, if you remove a variable, do the clauses containing that variable disappear, or do they still exist (with one less alternatives)?  Does it depend on whether the variable is negated in the clause or not?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-21T13:48:16.477Z
@Tsuyoshi: Let me be more precise than I previously were. If I remove a variable, the clauses containing that variable do not disappear (except in case of unit clauses): they still exist with one less alternative. It does not depend on whether the variable is negated in the clause or not: e.g. if we have clause $c = l_1 \lor \lnot l_2 \lor l_3$ and we remove variable $v_2$, such clause becomes $c = l_1 \lor l_3$.
Giorgio Camerani
CC BY-SA 2.5
2010-09-21T14:03:59.233Z
In my opinion you should state the definition of “removing a variable” in the question because it is far from obvious.  In particular, your previous comment implies that a unit clause disappears if the only variable in it is removed; this is counter-intuitive (almost contradictory) when compared to the other case, and has to be stated explicitly if that is really what you want.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-21T14:09:54.433Z
(Cont’d)  Also, I do not see any role played by the negation, and moreover I find the question stated in terms of CNF formula rather confusing because the definition of “removing a variable” does not seem to be any meaningful operation on CNF formulas such as assigning a value to a variable.  The question seems to be about a set system (or equivalently a hypergraph).
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-21T14:36:46.063Z
@Tsuyoshi: OK, I've improved the question. You're right in saying that the negation doesn't play any relevant role.
Giorgio Camerani
CC BY-SA 2.5
2010-09-21T19:43:15.937Z
Based on the comments, is this a correct reformulation? "Given a hypergraph chosen uniformly at random from among those with $n$ vertices and $m$ edges, what is the expected vertex connectivity of its Gaifman graph?"
András Salamon
CC BY-SA 2.5
2010-09-22T04:21:20.153Z
@Andras - I think it should be "Given a k-uniform hypergraph..."
Vinayak Pathak
CC BY-SA 2.5
2010-09-22T04:36:45.887Z
Also, I think it can be said that a hypergraph is connected if and only if its Gaifman graph is connected. So in that case what we are really asking is to find the average vertex connectivity of a k-uniform hypergraph. So we can as well start with the case when k = 2, that is, a graph. Does anyone know what's the average vertex connectivity of a graph?
Vinayak Pathak
CC BY-SA 2.5
2010-09-22T15:06:30.173Z
According to this post - http://mathoverflow.net/questions/28299/vertex-connectivity-of-random-graphs - on MO, the expected vertex connectivity of an Erdos-Renyi G(n, p) is pn as n approaches infinity. I think the analysis can be extended to the case of k-uniform hypergraphs too.
Vinayak Pathak
CC BY-SA 2.5
2010-09-22T16:48:50.227Z
@András: Nice reformulation!  Just to make sure, are you taking variables as vertices of the hypergraph?  In that case, according to the definition in [Wikipedia](http://en.wikipedia.org/wiki/Hypergraph#Terminology), we are speaking of the Gaifman graph of the _dual_ of this hypergraph, because there the Gaifman graph is defined as a synonym of the primal graph.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-22T20:59:04.207Z
There are so many comments that it might be a good idea to (1) close this question, and (2) create a new question that re-states it in terms of the average connectivity of random (hyper)graphs, with a link to this thread.
Jukka Suomela
CC BY-SA 2.5
2010-09-23T20:35:02.690Z
@Walter: @Jukka's point is a good one, this "thread" is becoming hard to follow without threading.
András Salamon
<ds.algorithms><sat>
Connected components of k-CNF formulas
Giorgio Camerani
# Connected components of k-CNF formulas

(Asked by: username_0 on 2010-09-21)

Let $F$ be a random k-CNF formula with $n$ variables and $m$ clauses. Let $G$ be the undirected graph built in the following manner: there is a vertex $v$ for every clause $c \in F$, and there is an edge $e = (v, u)$ if and only if the clause corresponding to $v$ has at least one variable in common with the clause corresponding to $u$.

The question is: how many variables, on average, shall I remove from $F$ before $G$ gets divided into 2 or more connected components? Is such number of variables related to $r = \frac{m}{n}$?

Here is what I mean by "removing a variable $v$ from a formula $F$": every clause $c$ in which $v$ is mentioned (no matter if positive or negative) gets shortened; if $c$ becomes empty, then it is removed from $F$.

**Tags:** ds.algorithms, sat
> **Comments:**
> **username_0**: Thanks, I'll reword the question. Jukka, did you see the last answer to my question "Monotone-2SAT and Vertex Cover"?  
> **username_2**: $G'$ does not seem to add anything to your setup, as it is simply a forest of cliques.  You seem to be asking about the average connectivity of $G$, but what is the distribution of functions?  
> **username_0**: I think you're right in saying that $G'$ doesn't add any value. Maybe I'll remove it from the question. Concerning your question, I forgot to say that the k-CNF formulas are random.  
> **username_2**: Are the k-CNF formulas chosen uniformly at random from among the ones with m clauses and n variables?  
> **username_0**: @Andras: Yes, they are.  
> **username_3**: 1. As András commented, the minimum number of vertices you have to remove to make a graph disconnected plus 1 is called the [(vertex) connectivity](http://en.wikipedia.org/wiki/K-vertex-connected_graph) of the graph.  If this is what you are interested in, adding this term may help reader to understand the question better.  2. You may want to add a reformulated version of the question without referring to CNF formulas because the negation does not play any role in the question.  
> **username_0**: @Tsuyoshi: $G$'s vertices correspond to $F$'s clauses: if I remove a vertex from $G$ it means I'm removing a clause from $F$. But I'm interested in removing variables of $F$, not clauses. Anyhow I feel that what Andras said is in some way related to what I'm asking. In other words: given a formula $F$, how many variables shall I remove (and which ones) in order that $F$ gets divided into 2 or more disjoint sub-formulas? Here "disjoint" means that the sub-formulas do not share any variable. @Andras: I don't see your comment any longer.  
> **username_3**: Oops, you are right.  The item 1 in my previous comment was wrong.  I realized that I did not understand the problem; what do you mean by removing a variable from a CNF formula?  More specifically, if you remove a variable, do the clauses containing that variable disappear, or do they still exist (with one less alternatives)?  Does it depend on whether the variable is negated in the clause or not?  
> **username_0**: @Tsuyoshi: Let me be more precise than I previously were. If I remove a variable, the clauses containing that variable do not disappear (except in case of unit clauses): they still exist with one less alternative. It does not depend on whether the variable is negated in the clause or not: e.g. if we have clause $c = l_1 \lor \lnot l_2 \lor l_3$ and we remove variable $v_2$, such clause becomes $c = l_1 \lor l_3$.  
> **username_3**: In my opinion you should state the definition of “removing a variable” in the question because it is far from obvious.  In particular, your previous comment implies that a unit clause disappears if the only variable in it is removed; this is counter-intuitive (almost contradictory) when compared to the other case, and has to be stated explicitly if that is really what you want.  (more)  
> **username_3**: (Cont’d)  Also, I do not see any role played by the negation, and moreover I find the question stated in terms of CNF formula rather confusing because the definition of “removing a variable” does not seem to be any meaningful operation on CNF formulas such as assigning a value to a variable.  The question seems to be about a set system (or equivalently a hypergraph).  
> **username_0**: @Tsuyoshi: OK, I've improved the question. You're right in saying that the negation doesn't play any relevant role.  
> **username_2**: Based on the comments, is this a correct reformulation? "Given a hypergraph chosen uniformly at random from among those with $n$ vertices and $m$ edges, what is the expected vertex connectivity of its Gaifman graph?"  
> **username_4**: @Andras - I think it should be "Given a k-uniform hypergraph..."  
> **username_4**: Also, I think it can be said that a hypergraph is connected if and only if its Gaifman graph is connected. So in that case what we are really asking is to find the average vertex connectivity of a k-uniform hypergraph. So we can as well start with the case when k = 2, that is, a graph. Does anyone know what's the average vertex connectivity of a graph?  
> **username_4**: According to this post - http://mathoverflow.net/questions/28299/vertex-connectivity-of-random-graphs - on MO, the expected vertex connectivity of an Erdos-Renyi G(n, p) is pn as n approaches infinity. I think the analysis can be extended to the case of k-uniform hypergraphs too.  
> **username_3**: @András: Nice reformulation!  Just to make sure, are you taking variables as vertices of the hypergraph?  In that case, according to the definition in [Wikipedia](http://en.wikipedia.org/wiki/Hypergraph#Terminology), we are speaking of the Gaifman graph of the _dual_ of this hypergraph, because there the Gaifman graph is defined as a synonym of the primal graph.  
> **username_5**: There are so many comments that it might be a good idea to (1) close this question, and (2) create a new question that re-states it in terms of the average connectivity of random (hyper)graphs, with a link to this thread.  
> **username_2**: @Walter: @Jukka's point is a good one, this "thread" is becoming hard to follow without threading.  
> **username_1**: Closed at request of original poster.  

---

## 0 answers

