2022/01/06 by Igor Razgon, Razgon, Igor
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2201.02173
openalex publication_date 2022/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 d-pw(G) and d-cpw(G) where G is a graph. We show that 2-cpw(G) ≤ O(tw(G) Δ(G)) where tw(G) and Δ(G) are, respectively the treewidth and maximal degree of G. Using this upper bound, we demonstrate that each CNF ψ can be represented as a conjunction of two OBDDs of size 2O(Δ(ψ)*tw(ψ)2) where tw(ψ) is the treewidth of the primal graph of ψ and each variable occurs in ψ at most Δ(ψ) times. Next we use d-pathwdith 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 ψ(G) whsose clauses are (u \vee e \vee v) for each edge e=\u,v\ of G. We prove that a d-SMNBP representing ψ(G) is of size at least Ω(cd-pw(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 ψ(Kn). In particular, we demonstrate that for each 0