Results 101 to 110 of about 5,860 (222)

The Treewidth of Line Graphs [PDF]

arXiv, 2014
The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph $G$ is equivalent to determining the minimum vertex congestion of an embedding of $G$ into a tree.
arxiv  

Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries [PDF]

Logical Methods in Computer Science
We show that the problem of whether a query is equivalent to a query of tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs).
Diego Figueira, Rémi Morvan
doaj   +1 more source

Non-FPT lower bounds for structural restrictions of decision DNNF [PDF]

arXiv, 2017
We give a non-FPT lower bound on the size of structured decision DNNF and OBDD with decomposable AND-nodes representing CNF-formulas of bounded incidence treewidth. Both models are known to be of FPT size for CNFs of bounded primal treewidth. To the best of our knowledge this is the first parameterized separation of primal treewidth and incidence ...
arxiv  

Treewidth of display graphs: bounds, brambles and applications [PDF]

arXiv, 2018
Phylogenetic trees and networks are leaf-labelled graphs used to model evolution. Display graphs are created by identifying common leaf labels in two or more phylogenetic trees or networks. The treewidth of such graphs is bounded as a function of many common dissimilarity measures between phylogenetic trees and this has been leveraged in fixed ...
arxiv  

Fast simulation of planar Clifford circuits [PDF]

Quantum
A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally ...
David Gosset, Daniel Grier, Alex Kerzner, Luke Schaeffer   +3 more
doaj   +1 more source

Characterizing width two for variants of treewidth [PDF]

arXiv, 2014
In this paper, we consider the notion of \emph{special treewidth}, recently introduced by Courcelle\cite{Courcelle2012}. In a special tree decomposition, for each vertex $v$ in a given graph, the bags containing $v$ form a rooted path. We show that the class of graphs of special treewidth at most two is closed under taking minors, and give the complete
arxiv  

Causal Unit Selection using Tractable Arithmetic Circuits

Proceedings of the International Florida Artificial Intelligence Research Society Conference
The unit selection problem aims to find objects, called units, that optimize a causal objective function which describes the objects' behavior in a causal context (e.g., selecting customers who are about to churn but would most likely change their mind ...
Haiying Huang, Adnan Darwiche
doaj   +1 more source

Minimum Fill-In and Treewidth for Graphs Modularly Decomposable into Chordal Graphs [PDF]

, 1998
Elias Dahlhaus
openalex   +1 more source

Treewidth Inapproximability and Tight ETH Lower Bound [PDF]

arXiv
We present a simple, self-contained, linear reduction from 3-SAT to Treewidth. Specifically, it shows that 1.00005-approximating Treewidth is NP-hard, and solving Treewidth exactly requires $2^{\Omega(n)}$ time, unless the Exponential-Time Hypothesis fails.
arxiv  

Complexity of Inference in Graphical Models [PDF]

arXiv, 2012
It is well-known that inference in graphical models is hard in the worst case, but tractable for models with bounded treewidth. We ask whether treewidth is the only structural criterion of the underlying graph that enables tractable inference. In other words, is there some class of structures with unbounded treewidth in which inference is tractable ...
arxiv