In this paper, we consider the notion of special treewidth, recently introduced by Courcelle (2012). 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 list of the six minor obstructions. As an intermediate result, we prove that every connected graph of special treewidth at most two can be constructed by arranging blocks of special treewidth at most two in a specific tree-like fashion.
Inspired by the notion of special treewidth, we introduce three natural variants of treewidth, namely spaghetti treewidth, strongly chordal treewidth and directed spaghetti treewidth. All these parameters lie between pathwidth and treewidth, and we provide common structural properties on these parameters. For each parameter, we prove that the class of graphs having the parameter at most two is minor closed, and we characterize those classes in terms of a tree of cycles with additional conditions. Finally, we show that for each k≥3, the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most k, is not closed under taking minors.
We introduce the graph theoretical parameter of edge-treewidth. This parameter occurs in a natural way as the tree-like analogue of cutwidth or, alternatively, as an edge-analogue of treewidth. We ...study the combinatorial properties of edge-treewidth. We first observe that edge-treewidth does not enjoy any closeness properties under the known partial ordering relations on graphs. We introduce a variant of the topological minor relation, namely, the weak topological minor relation and we prove that edge-treewidth is monotone with respect to weak topological minors. Based on this new relation we are able to provide universal obstructions for edge-treewidth. The proofs are based on the fact that edge-treewidth of a graph is parametrically equivalent with the maximum over the treewidth and the maximum degree of the blocks of the graph. We also prove that deciding whether the edge-treewidth of a graph is at most k is an NP-complete problem.
A graph H is an induced minor of a graph G if H can be obtained from G by vertex deletions and edge contractions. We show that there is a function f(k,d)=O(k10+2d5) so that if a graph has treewidth ...at least f(k,d) and maximum degree at most d, then it contains a k×k-grid as an induced minor. This proves the conjecture of Aboulker, Adler, Kim, Sintiari, and Trotignon (2021) 1 that any graph with large treewidth and bounded maximum degree contains a large wall or the line graph of a large wall as an induced subgraph. It also implies that for any fixed planar graph H, there is a subexponential time algorithm for maximum weight independent set on H-induced-minor-free graphs.
Answer Set Programming (ASP) is a paradigm for modeling and solving problems for knowledge representation and reasoning. There are plenty of results dedicated to studying the hardness of (fragments ...of) ASP. So far, these studies resulted in characterizations in terms of computational complexity as well as in fine-grained insights presented in form of dichotomy-style results, lower bounds when translating to other formalisms like propositional satisfiability (SAT), and even detailed parameterized complexity landscapes. A generic parameter in parameterized complexity originating from graph theory is the so-called treewidth, which in a sense captures structural density of a program. Recently, there was an increase in the number of treewidth-based solvers related to SAT. While there are translations from (normal) ASP to SAT, no reduction that preserves treewidth or at least keeps track of the treewidth increase is known. In this paper we propose a novel reduction from normal ASP to SAT that is aware of the treewidth, and guarantees that a slight increase of treewidth is indeed sufficient. Further, we show a new result establishing that, when considering treewidth, already the fragment of normal ASP is slightly harder than SAT (under reasonable assumptions in computational complexity). This also confirms that our reduction probably cannot be significantly improved and that the slight increase of treewidth is unavoidable. Finally, we present an empirical study of our novel reduction from normal ASP to SAT, where we compare treewidth upper bounds that are obtained via known decomposition heuristics. Overall, our reduction works better with these heuristics than existing translations.
PDF
