Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-160 | 1st October 2024 18:21

The splitting power of branching programs of bounded repetition and CNFs of bounded width

RSS-Feed




TR24-160
Authors: igor razgon
Publication: 20th October 2024 09:37
Downloads: 79
Keywords: 


Abstract:

In this paper we study syntactic branching programs of bounded repetition
representing CNFs of bounded treewidth.
For this purpose we introduce two new structural graph
parameters $d$-pathwidth and clique preserving $d$-pathwidth denoted
by $pw_d(G)$ and $cpw_d(G)$ where $G$ is a graph.
We show that $cpw_2(G) \leq O(tw(G) \Delta(G))$ where $tw(G)$ and $\Delta(G)$ are,
respectively the treewidth and maximal degree of $G$.
Using this upper bound, we demonstrate that each CNF $\psi$ can be represented
as a conjunction of two OBDDs (quite a restricted class of read-twice branching programs)
of size $2^{O(\Delta(\psi) \cdot tw(\psi)^2)}$ where $tw(\psi)$ is the treewidth of the primal graph of $\psi$
and each variable occurs in $\psi$ at most $\Delta(\psi)$ times.

Next, we use $d$-pathwidth to obtain lower bounds for monotone branching programs.
In particular, we consider the monotone version of syntactic nondeterministic read $d$ times
branching programs (just forbidding negative literals as edge labels) and introduce a further
restriction that each computational path can be partitioned into at most $d$ read-once subpaths.
We call the resulting model separable monotone read $d$ times branching programs and
abbreviate them $d$-SMNBPs. For each graph $G$ without isolated vertices, we introduce a CNF
$\psi(G)$ whose clauses are $(u \vee e \vee v)$ for each edge $e=\{u,v\}$ of $G$.
We prove that a $d$-SMNBP representing $\psi(G)$ is of size at least
$\Omega(c^{pw_d(G)})$ where $c=(8/7)^{1/12}$. We use this 'generic' lower bound to
obtain an exponential lower bound for a 'concrete' class of CNFs $\psi(K_n)$.
In particular, we demonstrate that for each $0<a<1$, the size of $n^{a}$-SMNBP representing
$\psi(K_n)$ is at least $c^{n^b}$ where $b$ is an arbitrary constant such that $a+b<1$.
This lower bound is tight in the sense $\psi(K_n)$ can be represented by a poly-sized
$n$-SMNBP.



ISSN 1433-8092 | Imprint