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, it stated that:

"The upper bound for this result was already known from [2] 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)$.

  • 3
    $\begingroup$ 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. $\endgroup$ Mar 6, 2023 at 19:46
  • $\begingroup$ @ArturRiazanov I would like to clarify if the definition of tree decomposition on hypergraph is as shown in NEIL ROBERTSON & SEYMOUR .1991.p168.. 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) $\endgroup$
    – Jxb
    Mar 7, 2023 at 3:23
  • 1
    $\begingroup$ @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))$ $\endgroup$
    – Jxb
    Aug 2, 2023 at 15:52


Your Answer

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