Skip to main content
deleted 1 character in body
Source Link
holf
  • 2.3k
  • 1
  • 16
  • 20

Notations and definitions: For a Boolean circuit $C$, the treewidth of $C$, $tw(C)$, is the treewidth of the underlying graph of $C$ where inputs having the same label have been identified. We denote by $tseit(C)$ the TseitingTseitin transform of $C$. It has one variable $x_u$ per gate of $C$. For each internal gates $u$ with input $u_1, \dots, u_k$ computing $f_u(u_1, \dots, u_k)$, it has several clauses $\mathcal{F}(u)$ on variables $x_u, x_{u_1}, \dots, x_{u_k}$. The conjunction of $\mathcal{F}$ is logically equivalent to $x_u \Leftrightarrow f(x_{u_1}, \dots, x_{u_k})$.

Notations and definitions: For a Boolean circuit $C$, the treewidth of $C$, $tw(C)$, is the treewidth of the underlying graph of $C$ where inputs having the same label have been identified. We denote by $tseit(C)$ the Tseiting transform of $C$. It has one variable $x_u$ per gate of $C$. For each internal gates $u$ with input $u_1, \dots, u_k$ computing $f_u(u_1, \dots, u_k)$, it has several clauses $\mathcal{F}(u)$ on variables $x_u, x_{u_1}, \dots, x_{u_k}$. The conjunction of $\mathcal{F}$ is logically equivalent to $x_u \Leftrightarrow f(x_{u_1}, \dots, x_{u_k})$.

Notations and definitions: For a Boolean circuit $C$, the treewidth of $C$, $tw(C)$, is the treewidth of the underlying graph of $C$ where inputs having the same label have been identified. We denote by $tseit(C)$ the Tseitin transform of $C$. It has one variable $x_u$ per gate of $C$. For each internal gates $u$ with input $u_1, \dots, u_k$ computing $f_u(u_1, \dots, u_k)$, it has several clauses $\mathcal{F}(u)$ on variables $x_u, x_{u_1}, \dots, x_{u_k}$. The conjunction of $\mathcal{F}$ is logically equivalent to $x_u \Leftrightarrow f(x_{u_1}, \dots, x_{u_k})$.

Source Link
holf
  • 2.3k
  • 1
  • 16
  • 20

There is a relation between the treewidth of a circuit and the primal treewidth of its Tseitin transformation but you will have to take the fan-in of the circuit into account, which is large when considering a naive circuit for $\neg \phi$ as you have a conjunction whose fan-in is the number of clauses of $\phi$ (even if you push the negation to the input to have a DNF-representation of $\neg \phi$, you have a large fan-in $\vee$-gate in the circuit).

Notations and definitions: For a Boolean circuit $C$, the treewidth of $C$, $tw(C)$, is the treewidth of the underlying graph of $C$ where inputs having the same label have been identified. We denote by $tseit(C)$ the Tseiting transform of $C$. It has one variable $x_u$ per gate of $C$. For each internal gates $u$ with input $u_1, \dots, u_k$ computing $f_u(u_1, \dots, u_k)$, it has several clauses $\mathcal{F}(u)$ on variables $x_u, x_{u_1}, \dots, x_{u_k}$. The conjunction of $\mathcal{F}$ is logically equivalent to $x_u \Leftrightarrow f(x_{u_1}, \dots, x_{u_k})$.

We have the following:

Lemma 1: The primal treewidth of $tseit(C)$ is at most $(k+1) \cdot (tw(C)+1)-1$, where $k$ is the fan-in of $C$.

Proof (sketch): Let $T$ be a tree decomposition of (the underlying graph of) $C$ of width $w$. We will transform it into a tree decomposition of $tseit(C)$. For every gate $u$ of $C$ with input $u_1, \dots, u_k$, there is a variable $x_u$ in $tseit(C)$ and clauses involving $x_u, x_{u_1}, \dots, x_{u_k}$.

We thus define $T'$ by replacing every occurrence of $u$ in $T$ by $x_u, x_{u_1}, \dots, x_{u_k}$. It can be verified that $T'$ is a tree decomposition of width $(k+1)(w+1)-1$ of the primal graph of $tseit(C)$.

$\square$

You cannot remove the dependency in the fan-in since a gate of fan-in $k$ in a circuit will be translated into a clause of size $(k+1)$ in $tseit(C)$, hence a $(k+1)$-clique in the primal graph. Artur Riazanov's comment shows that you cannot avoid this even by rewriting your large fan-in gates into trees of fan-in $2$.

This is however not the end of the story. You have a better relation between the incidence treewidth of $tseit(C)$ and the treewidth of $C$. And in turn, between the incidence treewidth of $\phi$ and the treewidth of $\neg \phi$.

I do not have any reference for this however and I would not tag it as folklore neither but it is known by some people working in parametrized complexity of SAT (I think the first time I discussed this was with Stefan Mengel on a simplification of the proof in [1, Section 4] showing thatbounded tw circuits can be transformed in FPT-size d-DNNF).

Lemma 2: The incidence treewidth of $tseit(C)$ is at most $2\cdot tw(C)+1$.

Proof: The incidence graph $G_C$ of $tseit(C)$ has vertices $x_u$ (corresponding to variable $x_u$ of $tseit(C)$) and $c_u$ (corresponding to clauses encoding that $x_u$ functionnally depends on $x_{u_1},\dots,x_{u_k}$) for each gate $u$ with input $u_1, \dots, u_k$. The edges of $G_C$ are of the form $(c_u, x_u)$ or $(c_u, x_v)$ where $v$ is an input of $u$, that is, when $(u,v)$ is an edge of $C$.

Thus, if $T$ is a tree decomposition of $C$ of width $w$, replacing occurrences of $u$ in $T$ by $C_u, x_u$ gives a tree decomposition $T'$ of $G_C$. Indeed, in $T'$, bags containing $x_u$ (or $c_u$) are connected since they exactly correspond to bags containing $u$ in $T$, which are connected by definition. And every edge of $G_C$ are covered in $T'$: edges of the form $(c_u, x_u)$ are covered in every bag of $T'$ corresponding to bags containing $u$ in $T$. And edges of the form $(c_u, x_v)$ are covered by the bag of $T'$ corresponding to the bag of $T$ containing both $u$ and $v$ (this bag exists since $(u,v)$ is an edge of $C$).

Clearly the largest bag of $T'$ has size $2(w+1)$ and thus, has treewidth $2w+1$.

$\square$

Now, interestingly, there is a clean relation between the incidence treewidth of a CNF $\phi$ and the treewidth of its circuit. Let $C_{\neg \phi}$ be the folowing circuit for $\neg \phi$: for each clause $c$ of $\phi$, we have a $\wedge$-gate $v_c$, for each variable $x$, we have a corresponding input $i_x$ labeled by $x$ and a negation gate $n_x$ having $i_x$ as input. If $x$ appears positively in clause $c$, we connect $n_x$ to $v_c$. If $x$ appears negatively in $c$, we connect $i_x$ to $v_c$. Finally, we have a large $\vee$-gate $v_{out}$ having every $v_c$ as input.

Lemma 3: Let $\phi$ be a CNF-formula of incidence treewidth $w$. $C_{\neg \phi}$ computes $\neg \phi$ and the treewidth of $C_{\neg \phi}$ is at most $2 \cdot (w+1)$.

Proof (sketch): $C_{\neg \phi}$ is clearly the circuit given by pushing the top negation of $\neg \phi$ to the input using De Morgan. Now given a tree decomposition of the incidence graph of $\phi$, it can be readily verified that we get a decomposition of $C_{\neg\phi}$ by replacing every occurrence of $c$ by $v_c$, every occurrence of $x$ by $n_x$ and $i_x$ and add $v_{out}$ in every bag.

$\square$

Lemma 1 and 2 together give:

Theorem: Let $\phi$ be a CNF-formula of incidence treewidth $w$. The incidence treewidth of $tseit(C_{\neg \phi})$ is at most $4w+5$.

References

[1] Connecting Knowledge Compilation Classes and Width Parameters, Antoine Amarilli, Florent Capelli, Mikaël Monet, Pierre Senellart, Theory of Computing Systems, 2020. https://arxiv.org/abs/1811.02944