<p>I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that <span class="math-container">$branchwidth(G) = Θ(treewidth(G))$</span>.</p>
<p>However, my question pertains to a specific case involving Tseitin formulas.</p>
<p>The <strong>underlying graph</strong> of Tseitin formulas is denoted by <span class="math-container">$G$</span>.</p>
<p>And the <strong>underlying hypergraph</strong> is denoted by <span class="math-container">$G'$</span> where each edge in the hypergraph corresponds to a clause of formulas.
<span class="math-container">$G$</span> and <span class="math-container">$G'$</span> can be seen as dual graphs, although a vertex in <span class="math-container">$G$</span> may correspond to multiple edges in <span class="math-container">$G'$</span>.</p>
<p><strong>Myquestion:</strong> What's the connection between <span class="math-container">$branchwidth(G')$</span> and <span class="math-container">$treewidth(G)$</span></p>
<p>My question comes from two papers, in <a href="https://arxiv.org/abs/2103.09609" rel="nofollow noreferrer">Characterizing Tseitin-formulas with short regular resolution refutations</a>, it stated that:</p>
<blockquote>
<p>&quot;The upper bound for this result was already known from <a href="http://people.cs.uchicago.edu/%7Erazborov/files/automat_pos.pdf" rel="nofollow noreferrer">[2]</a>
where it
is shown that, for every graph G, unsatisfiable Tseitin-formulas with
the underlying graph G have regular resolution refutations of length
at most <span class="math-container">$2^{O(tw(G))}|V (G)|^c$</span> where c is a constant.&quot;</p>
</blockquote>
<p>However, upon checking the reference, I noticed that it uses <span class="math-container">$branchwidth(G')$</span> rather than <span class="math-container">$treewidth(G)$</span>.</p>

CC BY-SA 4.0
2023-03-06T19:46:32.870Z
They differ by a factor $O(\Delta(G))$ where $\Delta(G)$ is the maximal degree of $G$. In the context of Tseitin formulas, it is usually assumed that the degree is constant, so this factor is dropped.
Artur Riazanov
CC BY-SA 4.0
2023-03-07T03:23:29.560Z
@ArturRiazanov  I would like to clarify if the definition of tree decomposition on hypergraph is as shown in  [NEIL ROBERTSON & SEYMOUR .1991.p168.](https://www.sciencedirect.com/science/article/pii/009589569190061N).  If this is the correct definition, I believe that the tree decomposition you obtained form $G$ to $G'$ by substituting every vertex of $G$ by the variables of the
incident edges may not satisfy condition (ii)
Jxb
CC BY-SA 4.0
2023-08-02T15:52:50.613Z
@ArturRiazanov Oh I understand your comment finally.  step1: for a same graph, treewidth is somewaht equals to branchwidth. step2: For a CNF, the treewidth of underlying hypergraph and primal graph is the same. step3: for Tseitin formulas, the treewidth of its primal graph and underlying grapg just differ by a factor $O(\Delta(G))$
Jxb
<graph-theory><sat><treewidth><fixed-parameter-tractable><proof-complexity>
What's the connection between branchwidth and treewidth
Jxb
# What's the connection between branchwidth and treewidth

(Asked by: username_0 on 2023-03-04)

I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that $branchwidth(G) = Θ(treewidth(G))$.

However, my question pertains to a specific case involving Tseitin formulas.

The **underlying graph** of Tseitin formulas is denoted by $G$.

And the **underlying hypergraph** is denoted by $G'$ where each edge in the hypergraph corresponds to a clause of formulas.
$G$ and $G'$ can be seen as dual graphs, although a vertex in $G$ may correspond to multiple edges in $G'$.

**Myquestion:** What's the connection between $branchwidth(G')$ and $treewidth(G)$

My question comes from two papers, in [Characterizing Tseitin-formulas with short regular resolution refutations](https://arxiv.org/abs/2103.09609), it stated that:

> "The upper bound for this result was already known from [[2]](http://people.cs.uchicago.edu/%7Erazborov/files/automat_pos.pdf)
> where it
> is shown that, for every graph G, unsatisfiable Tseitin-formulas with
> the underlying graph G have regular resolution refutations of length
> at most $2^{O(tw(G))}|V (G)|^c$ where c is a constant."

However, upon checking the reference, I noticed that it uses $branchwidth(G')$ rather than $treewidth(G)$.

**Tags:** graph-theory, sat, treewidth, fixed-parameter-tractable, proof-complexity

> **Comments:**
> **username_1**: They differ by a factor $O(\Delta(G))$ where $\Delta(G)$ is the maximal degree of $G$. In the context of Tseitin formulas, it is usually assumed that the degree is constant, so this factor is dropped.  
> **username_0**: @ArturRiazanov  I would like to clarify if the definition of tree decomposition on hypergraph is as shown in  [NEIL ROBERTSON & SEYMOUR .1991.p168.](https://www.sciencedirect.com/science/article/pii/009589569190061N).  If this is the correct definition, I believe that the tree decomposition you obtained form $G$ to $G'$ by substituting every vertex of $G$ by the variables of the incident edges may not satisfy condition (ii)  
> **username_0**: @ArturRiazanov Oh I understand your comment finally.  step1: for a same graph, treewidth is somewaht equals to branchwidth. step2: For a CNF, the treewidth of underlying hypergraph and primal graph is the same. step3: for Tseitin formulas, the treewidth of its primal graph and underlying grapg just differ by a factor $O(\Delta(G))$  

---

## 0 answers

