<p>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 <span class="math-container">$\neg \phi$</span> as you have a conjunction whose fan-in is the number of clauses of <span class="math-container">$\phi$</span> (even if you push the negation to the input to have a DNF-representation of <span class="math-container">$\neg \phi$</span>, you have a large fan-in <span class="math-container">$\vee$</span>-gate in the circuit).</p>
<p><strong>Notations and definitions</strong>: For a Boolean circuit <span class="math-container">$C$</span>, the <em>treewidth</em> of <span class="math-container">$C$</span>, <span class="math-container">$tw(C)$</span>, is the treewidth of the underlying graph of <span class="math-container">$C$</span> where inputs having the same label have been identified. We denote by <span class="math-container">$tseit(C)$</span> the Tseitin transform of <span class="math-container">$C$</span>. It has one variable <span class="math-container">$x_u$</span> per gate of <span class="math-container">$C$</span>. For each internal gates <span class="math-container">$u$</span> with input <span class="math-container">$u_1, \dots, u_k$</span> computing <span class="math-container">$f_u(u_1, \dots, u_k)$</span>, it has several clauses <span class="math-container">$\mathcal{F}(u)$</span> on variables <span class="math-container">$x_u, x_{u_1}, \dots, x_{u_k}$</span>. The conjunction of <span class="math-container">$\mathcal{F}$</span> is logically equivalent to <span class="math-container">$x_u \Leftrightarrow f(x_{u_1}, \dots, x_{u_k})$</span>.</p>
<p>We have the following:</p>
<p><strong>Lemma 1</strong>: The primal treewidth of <span class="math-container">$tseit(C)$</span> is at most <span class="math-container">$(k+1) \cdot (tw(C)+1)-1$</span>, where <span class="math-container">$k$</span> is the fan-in of <span class="math-container">$C$</span>.</p>
<p><em>Proof (sketch)</em>: Let <span class="math-container">$T$</span> be a tree decomposition of (the underlying graph of) <span class="math-container">$C$</span> of width <span class="math-container">$w$</span>. We will transform it into a tree decomposition of <span class="math-container">$tseit(C)$</span>. For every gate <span class="math-container">$u$</span> of <span class="math-container">$C$</span> with input <span class="math-container">$u_1, \dots, u_k$</span>, there is a variable <span class="math-container">$x_u$</span> in <span class="math-container">$tseit(C)$</span> and clauses involving <span class="math-container">$x_u, x_{u_1}, \dots, x_{u_k}$</span>.</p>
<p>We thus define <span class="math-container">$T'$</span> by replacing every occurrence of <span class="math-container">$u$</span> in <span class="math-container">$T$</span> by <span class="math-container">$x_u, x_{u_1}, \dots, x_{u_k}$</span>. It can be verified that <span class="math-container">$T'$</span> is a tree decomposition of width <span class="math-container">$(k+1)(w+1)-1$</span> of the primal graph of <span class="math-container">$tseit(C)$</span>.</p>
<p><span class="math-container">$\square$</span></p>
<p>You cannot remove the dependency in the fan-in since a gate of fan-in <span class="math-container">$k$</span> in a circuit will be translated into a clause of size <span class="math-container">$(k+1)$</span> in <span class="math-container">$tseit(C)$</span>, hence a <span class="math-container">$(k+1)$</span>-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 <span class="math-container">$2$</span>.</p>
<p>This is however not the end of the story. You have a better relation between the incidence treewidth of <span class="math-container">$tseit(C)$</span> and the treewidth of <span class="math-container">$C$</span>. And in turn, between the incidence treewidth of <span class="math-container">$\phi$</span> and the treewidth of <span class="math-container">$\neg \phi$</span>.</p>
<p>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).</p>
<p><strong>Lemma 2</strong>: The incidence treewidth of <span class="math-container">$tseit(C)$</span> is at most <span class="math-container">$2\cdot tw(C)+1$</span>.</p>
<p><em>Proof:</em> The incidence graph <span class="math-container">$G_C$</span> of <span class="math-container">$tseit(C)$</span> has vertices <span class="math-container">$x_u$</span> (corresponding to variable <span class="math-container">$x_u$</span> of <span class="math-container">$tseit(C)$</span>) and <span class="math-container">$c_u$</span> (corresponding to clauses encoding that <span class="math-container">$x_u$</span> functionnally depends on <span class="math-container">$x_{u_1},\dots,x_{u_k}$</span>) for each gate <span class="math-container">$u$</span> with input <span class="math-container">$u_1, \dots, u_k$</span>. The edges of <span class="math-container">$G_C$</span> are of the form <span class="math-container">$(c_u, x_u)$</span> or <span class="math-container">$(c_u, x_v)$</span> where <span class="math-container">$v$</span> is an input of <span class="math-container">$u$</span>, that is, when <span class="math-container">$(u,v)$</span> is an edge of <span class="math-container">$C$</span>.</p>
<p>Thus, if <span class="math-container">$T$</span> is a tree decomposition of <span class="math-container">$C$</span> of width <span class="math-container">$w$</span>, replacing occurrences of <span class="math-container">$u$</span> in <span class="math-container">$T$</span> by <span class="math-container">$C_u, x_u$</span> gives a tree decomposition <span class="math-container">$T'$</span> of <span class="math-container">$G_C$</span>. Indeed, in <span class="math-container">$T'$</span>, bags containing <span class="math-container">$x_u$</span> (or <span class="math-container">$c_u$</span>) are connected since they exactly correspond to bags containing <span class="math-container">$u$</span> in <span class="math-container">$T$</span>, which are connected by definition. And every edge of <span class="math-container">$G_C$</span> are covered in <span class="math-container">$T'$</span>: edges of the form <span class="math-container">$(c_u, x_u)$</span> are covered in every bag of <span class="math-container">$T'$</span> corresponding to bags containing <span class="math-container">$u$</span> in <span class="math-container">$T$</span>. And edges of the form <span class="math-container">$(c_u, x_v)$</span> are covered by the bag of <span class="math-container">$T'$</span> corresponding to the bag of <span class="math-container">$T$</span> containing both <span class="math-container">$u$</span> and <span class="math-container">$v$</span> (this bag exists since <span class="math-container">$(u,v)$</span> is an edge of <span class="math-container">$C$</span>).</p>
<p>Clearly the largest bag of <span class="math-container">$T'$</span> has size <span class="math-container">$2(w+1)$</span> and thus, has treewidth <span class="math-container">$2w+1$</span>.</p>
<p><span class="math-container">$\square$</span></p>
<p>Now, interestingly, there is a clean relation between the incidence treewidth of a CNF <span class="math-container">$\phi$</span> and the treewidth of its circuit. Let <span class="math-container">$C_{\neg \phi}$</span> be the folowing circuit for <span class="math-container">$\neg \phi$</span>: for each clause <span class="math-container">$c$</span> of <span class="math-container">$\phi$</span>, we have a <span class="math-container">$\wedge$</span>-gate <span class="math-container">$v_c$</span>, for each variable <span class="math-container">$x$</span>, we have a corresponding input <span class="math-container">$i_x$</span> labeled by <span class="math-container">$x$</span> and a negation gate <span class="math-container">$n_x$</span> having <span class="math-container">$i_x$</span> as input. If <span class="math-container">$x$</span> appears positively in clause <span class="math-container">$c$</span>, we connect  <span class="math-container">$n_x$</span> to <span class="math-container">$v_c$</span>. If <span class="math-container">$x$</span> appears negatively in <span class="math-container">$c$</span>, we connect <span class="math-container">$i_x$</span> to <span class="math-container">$v_c$</span>. Finally, we have a large <span class="math-container">$\vee$</span>-gate <span class="math-container">$v_{out}$</span> having every <span class="math-container">$v_c$</span> as input.</p>
<p><strong>Lemma 3</strong>: Let <span class="math-container">$\phi$</span> be a CNF-formula of incidence treewidth <span class="math-container">$w$</span>. <span class="math-container">$C_{\neg \phi}$</span> computes <span class="math-container">$\neg \phi$</span> and the treewidth of <span class="math-container">$C_{\neg \phi}$</span> is at most <span class="math-container">$2 \cdot (w+1)$</span>.</p>
<p><em>Proof (sketch)</em>: <span class="math-container">$C_{\neg \phi}$</span> is clearly the circuit given by pushing the top negation of <span class="math-container">$\neg \phi$</span> to the input using De Morgan. Now given a tree decomposition of the incidence graph of <span class="math-container">$\phi$</span>, it can be readily verified that we get a decomposition of <span class="math-container">$C_{\neg\phi}$</span> by replacing every occurrence of <span class="math-container">$c$</span> by <span class="math-container">$v_c$</span>, every occurrence of <span class="math-container">$x$</span> by <span class="math-container">$n_x$</span> and <span class="math-container">$i_x$</span> and add <span class="math-container">$v_{out}$</span> in every bag.</p>
<p><span class="math-container">$\square$</span></p>
<p>Lemma 1 and 2 together give:</p>
<p><strong>Theorem</strong>: Let <span class="math-container">$\phi$</span> be a CNF-formula of incidence treewidth <span class="math-container">$w$</span>. The incidence treewidth of <span class="math-container">$tseit(C_{\neg \phi})$</span> is at most <span class="math-container">$4w+5$</span>.</p>
<h1>References</h1>
<p>[1] Connecting Knowledge Compilation Classes and Width Parameters, Antoine Amarilli, Florent Capelli, Mikaël Monet, Pierre Senellart, Theory of Computing Systems, 2020. <a href="https://arxiv.org/abs/1811.02944" rel="nofollow noreferrer">https://arxiv.org/abs/1811.02944</a></p>

CC BY-SA 4.0
2022-04-19T05:28:27.370Z
2022-04-19T06:38:21.220Z
2022-04-19T06:38:21.220Z
holf
<p>Actually, we can transform any Boolean Circuit <span class="math-container">$C$</span> that uses only <span class="math-container">$\wedge$</span>, <span class="math-container">$\vee$</span>, and <span class="math-container">$\neg$</span> gates of treewidth <span class="math-container">$k$</span> into a CNF whose primal treewidth is within a constant factor of <span class="math-container">$k$</span>, where this constant factor does <em>not</em> depend on the fan-in/fan-out.</p>
<p>However, in order to do this, we need to be given a tree decomposition of <span class="math-container">$C$</span> that has width <span class="math-container">$k$</span>.</p>
<p>In fact, we can prove the following:</p>
<p><strong>Lemma</strong>:
Let <span class="math-container">$C$</span> be a circuit and <span class="math-container">$(T,\chi)$</span> a tree decomposition of <span class="math-container">$C$</span> with width <span class="math-container">$k$</span>. Then we can construct in polynomial time a CNF <span class="math-container">$\phi$</span> such that <span class="math-container">$C$</span> and <span class="math-container">$\phi$</span> have the same number of models, have the same models restricted to the original labels of <span class="math-container">$C$</span>, and such that the primal treewidth of <span class="math-container">$\phi$</span> is less or equal to <span class="math-container">$4(k+1)$</span>.</p>
<p>Intuitively, this works by introducing auxiliary variables <span class="math-container">$v_{x,t}$</span> for each gate <span class="math-container">$x$</span> and vertex <span class="math-container">$t$</span> of the tree decomposition, where <span class="math-container">$v_{x,t}$</span> denotes the truth value of the gate <span class="math-container">$x$</span> taking into account the inputs that occur in <span class="math-container">$t$</span> or below in the tree decomposition.</p>
<p><strong>Proof</strong>:
We let <span class="math-container">$\ell(x)$</span> for <span class="math-container">$x$</span> a gate in <span class="math-container">$C$</span> denote the label/type of the gate <span class="math-container">$x$</span>. For inputs <span class="math-container">$v \in \mathcal{V}$</span>, we let <span class="math-container">$\ell(v) = v$</span>.</p>
<p>Let <span class="math-container">$(T, \chi)$</span> be a tree decomposition of width <span class="math-container">$k$</span> for <span class="math-container">$C$</span>. We construct a CNF <span class="math-container">$\psi$</span> as the set containing the following clauses:</p>
<ul>
<li>for <span class="math-container">$x \in \chi(t), \ell(x) = \wedge$</span> we add
<span class="math-container">\begin{align*}
    v_{x,t} \leftrightarrow \left(\bigwedge_{t' \in child(t), x \in \chi(t')} v_{x,t'} \right) \wedge \left(\bigwedge_{y \in parent(x), y \in \chi(t)} y\right),
\end{align*}</span>
where <span class="math-container">$child(t)$</span> is the set of children (i.e. direct descendants) of <span class="math-container">$t$</span> in the tree <span class="math-container">$T$</span> and <span class="math-container">$parent(x)$</span> is the set of parents (i.e. direct ancestors) of <span class="math-container">$x$</span> in the DAG <span class="math-container">$C$</span>.</li>
<li>for <span class="math-container">$x \in \chi(t), \ell(x) = \vee$</span> we add
<span class="math-container">\begin{align*}
    v_{x,t} \leftrightarrow \left(\bigvee_{t' \in child(t), x \in \chi(t')} v_{x,t'} \right) \vee \left(\bigvee_{y \in parent(x), y \in \chi(t)} y\right),
\end{align*}</span>
where <span class="math-container">$child(t)$</span> is the set of children (i.e. direct descendants) of <span class="math-container">$t$</span> in the tree <span class="math-container">$T$</span> and <span class="math-container">$parent(x)$</span> is the set of parents (i.e. direct ancestors) of <span class="math-container">$x$</span> in the DAG <span class="math-container">$C$</span>.</li>
<li>for <span class="math-container">$x,y \in \chi(t), \ell(x) = \neg, parent(x) = \{y\}$</span> we add
<span class="math-container">$$
x \leftrightarrow \neg y
$$</span></li>
<li>for <span class="math-container">$x_{root}$</span> the output node of <span class="math-container">$C$</span>
<span class="math-container">$$
x_{root}
$$</span>
Finally, we obtain <span class="math-container">$\phi$</span> by replacing, for <span class="math-container">$x \in \chi(t), \ell(x) \in \{\wedge, \vee\}, x \not \in t', \{t'\} = parent(t)$</span>, the variable <span class="math-container">$x$</span> by <span class="math-container">$v_{x,t}$</span> in every clause of <span class="math-container">$\psi$</span>.</li>
</ul>
<p>We define <span class="math-container">$(T, \chi')$</span>, a tree decomposition for <span class="math-container">$\phi$</span>, by letting
<span class="math-container">\begin{align*}
\chi'(t) = \chi(t) \cup \{v_{x,t'} \mid x \in \chi(t')\cap \chi(t), t' \in child(t) \cup \{t\}, \ell(x) \not\in \mathcal{V}\}.
\end{align*}</span>
Since, w.l.o.g., we can assume that for each <span class="math-container">$t \in V(T)$</span> it holds that <span class="math-container">$|child(t)| \leq 2$</span> (this holds for example when we have a <em>nice tree decomposition</em> [1]) we see that
<span class="math-container">\begin{align*}
|\chi'(t)| &amp;= |\chi(t) \cup \{v_{x,t'} \mid x \in \chi(t')\cap \chi(t), t' \in child(t) \cup \{t\}, \ell(x) \not\in \mathcal{V}\}|\\
           &amp;= |\chi(t)| + |\{v_{x,t'} \mid x \in \chi(t')\cap \chi(t), t' \in child(t) \cup \{t\}, \ell(x) \not\in \mathcal{V}\}|\\
    &amp;\leq  k + 1 + 3(k+1) = 4(k + 1)
\end{align*}</span></p>
<p><span class="math-container">$\square$</span></p>
<p>Note that actually an even tighter bound of <span class="math-container">$3(k+1)$</span> holds for this construction. This is shown by not adding <span class="math-container">$v_(x,t)$</span> and <span class="math-container">$v(x,t')$</span> for the children <span class="math-container">$t'$</span> all at the same time. Instead, we have <span class="math-container">$v(x,t')$</span> for the both children in the beginning. Then, we add <span class="math-container">$v(x, t)$</span>, allowing us to remove <span class="math-container">$v(x,t')$</span> for the children. By doing this step by step for each of the gates <span class="math-container">$x$</span> we obtain the desired bound.</p>
<p>Thus, to answer the original question is you have a circuit <span class="math-container">$C$</span> of treewidth <span class="math-container">$k$</span>, then there is a circuit <span class="math-container">$C'$</span> which corresponds to the negation of <span class="math-container">$C$</span> (we just add an additional gate that negates the output gate of <span class="math-container">$C$</span>) of treewidth <span class="math-container">$k$</span> (<span class="math-container">$+1$</span> if the treewidth of <span class="math-container">$C$</span> was <span class="math-container">$0$</span>). Then we can use the construction in the proof of the above lemma to obtain a CNF representing <span class="math-container">$C$</span> with primal treewidth <span class="math-container">$3(k + 1)$</span>.</p>
<p>References:</p>
<p>[1] Ernst Althaus and Sarah Ziegler. Optimal tree decompositions revisited: A simpler linear-time fpt algorithm. arXiv preprint arXiv:1912.09144, 2019.</p>

CC BY-SA 4.0
2022-12-09T15:53:21.820Z
Interesting, I never tried to have this result directly as incidence treewidth is usually enough for tractability. Now, you could recover this result from my Lemma 2 + and an adaptation of Lemma 4 (a bit hidden) of Marko Samer, Stefan Szeider:
Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci. 76(2): 103-114 (2010) where they "roughly" prove that a CNF of itw k can be encoded into a 3-CNF of itw k, hence of primal treewdith 3k.
holf
CC BY-SA 4.0
2022-12-12T12:01:34.893Z
Yes that makes sense. Thank you for the reference.
raki123
CC BY-SA 4.0
2022-12-12T13:03:25.843Z
You are welcome. This is a nice paper but what is proven in Lemma 4 is not spilled out as I have written it in my previous comment hence the result is not that well-known. Actually, Stefan Szeider told me about it or I would have missed the connection!
holf
CC BY-SA 4.0
2022-12-09T10:57:05.017Z
2022-12-09T11:01:19.073Z
2022-12-09T11:01:19.073Z
raki123
<p>Suppose you have a propositional formula <span class="math-container">$\varphi$</span> in CNF. You want to efficiently obtain an equisatisfiable CNF formula encoding <span class="math-container">$\neg \varphi$</span>. You use the usual Tseitin encoding with auxiliary variables. Now,</p>
<p><strong>Question</strong>. If the primal treewidth of <span class="math-container">$\varphi$</span> is <span class="math-container">$k$</span>, what is the primal treewidth of <span class="math-container">$\neg\varphi$</span> after transforming into CNF via the Tseitin procedure? Is it bounded by some function of <span class="math-container">$k$</span>, or does it depend on the entire size of <span class="math-container">$\varphi$</span>?</p>
<p>Here by <em>primal treewidth</em> I mean the treewidth of the primal graph of <span class="math-container">$\varphi$</span>, that is, the graph where the nodes are the variables of the formula and two nodes are connected if the corresponding variables appear together in some clause.</p>

CC BY-SA 4.0
2022-04-18T17:42:14.623Z
Seems that in some cases it can increase quite a bit and it depends on the particular way you represent $\lnot \phi$ as a circuit. Consider a CNF $\phi = \bigwedge_{i \in [n-1]}(x_i \lor x_{i+1})$. Its primal graph is a path. Then let the large conjunction in $\phi$ be represented as a tree such that $(x_i \lor x_{i+1})$ and $(x_{i+\sqrt{n}} \lor x_{i+\sqrt{n}+1})$ share the parent. Then the primal graph of the new formula should have a $\Omega(\sqrt{n}) \times \Omega(\sqrt{n})$ grid minor.
Artur Riazanov
<cc.complexity-theory><parameterized-complexity><treewidth><boolean-formulas><encoding>
Treewidth relations between Boolean formulas and Tseitin encodings
Noel Arteche
# Treewidth relations between Boolean formulas and Tseitin encodings

(Asked by: username_0 on 2022-04-18)

Suppose you have a propositional formula $\varphi$ in CNF. You want to efficiently obtain an equisatisfiable CNF formula encoding $\neg \varphi$. You use the usual Tseitin encoding with auxiliary variables. Now,

**Question**. If the primal treewidth of $\varphi$ is $k$, what is the primal treewidth of $\neg\varphi$ after transforming into CNF via the Tseitin procedure? Is it bounded by some function of $k$, or does it depend on the entire size of $\varphi$?

Here by *primal treewidth* I mean the treewidth of the primal graph of $\varphi$, that is, the graph where the nodes are the variables of the formula and two nodes are connected if the corresponding variables appear together in some clause.

**Tags:** cc.complexity-theory, parameterized-complexity, treewidth, boolean-formulas, encoding
> **Comments:**
> **username_1**: Seems that in some cases it can increase quite a bit and it depends on the particular way you represent $\lnot \phi$ as a circuit. Consider a CNF $\phi = \bigwedge_{i \in [n-1]}(x_i \lor x_{i+1})$. Its primal graph is a path. Then let the large conjunction in $\phi$ be represented as a tree such that $(x_i \lor x_{i+1})$ and $(x_{i+\sqrt{n}} \lor x_{i+\sqrt{n}+1})$ share the parent. Then the primal graph of the new formula should have a $\Omega(\sqrt{n}) \times \Omega(\sqrt{n})$ grid minor.  

---

## 2 answers

### Answer by username_2 on 2022-04-19. Score: 5 | Accepted answer

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

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>


---

### Answer by username_3 on 2022-12-09. Score: 4

Actually, we can transform any Boolean Circuit $C$ that uses only $\wedge$, $\vee$, and $\neg$ gates of treewidth $k$ into a CNF whose primal treewidth is within a constant factor of $k$, where this constant factor does *not* depend on the fan-in/fan-out.

However, in order to do this, we need to be given a tree decomposition of $C$ that has width $k$.

In fact, we can prove the following:

**Lemma**:
Let $C$ be a circuit and $(T,\chi)$ a tree decomposition of $C$ with width $k$. Then we can construct in polynomial time a CNF $\phi$ such that $C$ and $\phi$ have the same number of models, have the same models restricted to the original labels of $C$, and such that the primal treewidth of $\phi$ is less or equal to $4(k+1)$.

Intuitively, this works by introducing auxiliary variables $v\_{x,t}$ for each gate $x$ and vertex $t$ of the tree decomposition, where $v\_{x,t}$ denotes the truth value of the gate $x$ taking into account the inputs that occur in $t$ or below in the tree decomposition.

**Proof**:
We let $\ell(x)$ for $x$ a gate in $C$ denote the label/type of the gate $x$. For inputs $v \in \mathcal{V}$, we let $\ell(v) = v$.

Let $(T, \chi)$ be a tree decomposition of width $k$ for $C$. We construct a CNF $\psi$ as the set containing the following clauses:

* for $x \in \chi(t), \ell(x) = \wedge$ we add
  \begin{align\*}
  v\_{x,t} \leftrightarrow \left(\bigwedge\_{t' \in child(t), x \in \chi(t')} v\_{x,t'} \right) \wedge \left(\bigwedge\_{y \in parent(x), y \in \chi(t)} y\right),
  \end{align\*}
  where $child(t)$ is the set of children (i.e. direct descendants) of $t$ in the tree $T$ and $parent(x)$ is the set of parents (i.e. direct ancestors) of $x$ in the DAG $C$.
* for $x \in \chi(t), \ell(x) = \vee$ we add
  \begin{align\*}
  v\_{x,t} \leftrightarrow \left(\bigvee\_{t' \in child(t), x \in \chi(t')} v\_{x,t'} \right) \vee \left(\bigvee\_{y \in parent(x), y \in \chi(t)} y\right),
  \end{align\*}
  where $child(t)$ is the set of children (i.e. direct descendants) of $t$ in the tree $T$ and $parent(x)$ is the set of parents (i.e. direct ancestors) of $x$ in the DAG $C$.
* for $x,y \in \chi(t), \ell(x) = \neg, parent(x) = \{y\}$ we add
  $$
  x \leftrightarrow \neg y
  $$
* for $x\_{root}$ the output node of $C$
  $$
  x\_{root}
  $$
  Finally, we obtain $\phi$ by replacing, for $x \in \chi(t), \ell(x) \in \{\wedge, \vee\}, x \not \in t', \{t'\} = parent(t)$, the variable $x$ by $v\_{x,t}$ in every clause of $\psi$.

We define $(T, \chi')$, a tree decomposition for $\phi$, by letting
\begin{align\*}
\chi'(t) = \chi(t) \cup \{v\_{x,t'} \mid x \in \chi(t')\cap \chi(t), t' \in child(t) \cup \{t\}, \ell(x) \not\in \mathcal{V}\}.
\end{align\*}
Since, w.l.o.g., we can assume that for each $t \in V(T)$ it holds that $|child(t)| \leq 2$ (this holds for example when we have a *nice tree decomposition* [1]) we see that
\begin{align\*}
|\chi'(t)| &= |\chi(t) \cup \{v\_{x,t'} \mid x \in \chi(t')\cap \chi(t), t' \in child(t) \cup \{t\}, \ell(x) \not\in \mathcal{V}\}|\\
&= |\chi(t)| + |\{v\_{x,t'} \mid x \in \chi(t')\cap \chi(t), t' \in child(t) \cup \{t\}, \ell(x) \not\in \mathcal{V}\}|\\
&\leq k + 1 + 3(k+1) = 4(k + 1)
\end{align\*}

$\square$

Note that actually an even tighter bound of $3(k+1)$ holds for this construction. This is shown by not adding $v\_(x,t)$ and $v(x,t')$ for the children $t'$ all at the same time. Instead, we have $v(x,t')$ for the both children in the beginning. Then, we add $v(x, t)$, allowing us to remove $v(x,t')$ for the children. By doing this step by step for each of the gates $x$ we obtain the desired bound.

Thus, to answer the original question is you have a circuit $C$ of treewidth $k$, then there is a circuit $C'$ which corresponds to the negation of $C$ (we just add an additional gate that negates the output gate of $C$) of treewidth $k$ ($+1$ if the treewidth of $C$ was $0$). Then we can use the construction in the proof of the above lemma to obtain a CNF representing $C$ with primal treewidth $3(k + 1)$.

References:

[1] Ernst Althaus and Sarah Ziegler. Optimal tree decompositions revisited: A simpler linear-time fpt algorithm. arXiv preprint arXiv:1912.09144, 2019.

> **Comments:**
> **username_2**: Interesting, I never tried to have this result directly as incidence treewidth is usually enough for tractability. Now, you could recover this result from my Lemma 2 + and an adaptation of Lemma 4 (a bit hidden) of Marko Samer, Stefan Szeider: Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci. 76(2): 103-114 (2010) where they "roughly" prove that a CNF of itw k can be encoded into a 3-CNF of itw k, hence of primal treewdith 3k.  
> **username_3**: Yes that makes sense. Thank you for the reference.  
> **username_2**: You are welcome. This is a nice paper but what is proven in Lemma 4 is not spilled out as I have written it in my previous comment hence the result is not that well-known. Actually, Stefan Szeider told me about it or I would have missed the connection!  

---

