Results 31 to 40 of about 13,679 (262)
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2023 The core chase, a popular algorithm for answering conjunctive queries (CQs) over existential rules, is guaranteed to terminate and compute a finite universal model whenever one exists, leading to the equivalence of the universal-model-based and the chase-
Jean-François Baget +2 more
semanticscholar +1 more source
Twin-width can be exponential in treewidth [PDF]
J. Comb. Theory B, 2022 For any small positive real $\varepsilon$ and integer $t>\frac{1}{\varepsilon}$, we build a graph with a vertex deletion set of size $t$ to a tree, and twin-width greater than $2^{(1-\varepsilon) t}$.
Édouard Bonnet, Hugues Déprés
semanticscholar +1 more source
Treewidth, Circle Graphs, and Circular Drawings [PDF]
SIAM Journal on Discrete Mathematics, 2022 A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects'.
Robert Hickingbotham +3 more
semanticscholar +1 more source
On treewidth approximations [PDF]
Electronic Notes in Discrete Mathematics, 2001 AbstractWe introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a different technique, we give a O(logk) approximation algorithm for the treewidth of arbitrary graphs, where k is the treewidth of the ...
Bouchitté, Vincent +3 more
openaire +4 more sources
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth [PDF]
Symposium on the Theory of Computing, 2022 We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth-r graph, there exists a (fractional) multicommodity flow of value f, and a multicut of capacity c such that f
T. Friedrich +4 more
semanticscholar +1 more source
The treewidth and pathwidth of graph unions [PDF]
SIAM Journal on Discrete Mathematics, 2022 Given two $n$-vertex graphs $G_1$ and $G_2$ of bounded treewidth, is there an $n$-vertex graph $G$ of bounded treewidth having subgraphs isomorphic to $G_1$ and $G_2$? Our main result is a negative answer to this question, in a strong sense: we show that
Bogdan Alecu +5 more
semanticscholar +1 more source
Answer Counting under Guarded TGDs [PDF]
Logical Methods in Computer Science, 2023 We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language ...
Cristina Feier +2 more
doaj +1 more source
Computing Treewidth on the GPU
arXiv, 2017 We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an $O^*(2^{n})$-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach.
Tom C. van der Zanden +1 more
openalex +8 more sources
Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth [PDF]
Advances in Combinatorics, 2021 A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $\mathcal{H}$ of graphs, we say a graph $G$ is $\mathcal{H}$-_free_ if no induced subgraph of $G$ is ...
Tara Abrishami +3 more
semanticscholar +1 more source
Extension Complexity, MSO Logic, and Treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 We consider the convex hull $P_{\varphi}(G)$ of all satisfying assignments of a given MSO formula $\varphi$ on a given graph $G$. We show that there exists an extended formulation of the polytope $P_{\varphi}(G)$ that can be described by $f(|\varphi ...
Petr Kolman +2 more
doaj +1 more source