Results 221 to 230 of about 4,791 (239)

Treewidth Is NP-Complete on Cubic Graphs

International Symposium on Parameterized and Exact Computation
In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9.
H. Bodlaender, Édouard Bonnet, L. Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanič, S. Ordyniak, Sukanya Pandey, Ondrej Suchý   +8 more
semanticscholar   +1 more source

Every Graph is Essential to Large Treewidth

arXiv.org
We show that for every graph $H$, there is a hereditary weakly sparse graph class $\mathcal C_H$ of unbounded treewidth such that the $H$-free (i.e., excluding $H$ as an induced subgraph) graphs of $\mathcal C_H$ have bounded treewidth.
Bogdan Alecu, Édouard Bonnet, Pedro Bureo Villafana, Nicolas Trotignon   +3 more
semanticscholar   +1 more source

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star

arXiv.org
Many recent works address the question of characterizing induced obstructions to bounded treewidth. In 2022, Lozin and Razgon completely answered this question for graph classes defined by finitely many forbidden induced subgraphs.
Clément Dallard, Matjaž Krnc, O.-joung Kwon, Martin Milanič, Andrea Munaro, Kenny Štorgel, Sebastian Wiederrecht   +6 more
semanticscholar   +1 more source

On treewidth and maximum cliques

Innovations in Graph Theory
We construct classes of graphs that are variants of the so-called layered wheel. One of their key properties is that while the treewidth is bounded by a function of the clique number, the construction can be adjusted to make the dependence grow ...
Maria Chudnovsky, Nicolas Trotignon
semanticscholar   +1 more source

Faster Sampling Algorithms for Polytopes with Small Treewidth

BigData Congress [Services Society]
Sampling is a fundamental problem in optimization, machine learning and theoretical computer science. A common region of interest for sampling is the polytope, which is defined by a set of linear inequalities.
Yekun Ke, Xiaoyu Li, Zhao Song, Tianyi Zhou   +3 more
semanticscholar   +1 more source

Treewidth Inapproximability and Tight ETH Lower Bound

Symposium on the Theory of Computing
Despite the (algorithmic) importance of treewidth, both its complexity and approximability present large knowledge gaps. While the best currently known polynomial-time approximation algorithm has ratio O(√logOPT), no approximation factor could be ruled ...
Édouard Bonnet
semanticscholar   +1 more source

Excluding a Clique or a Biclique in Graphs of Bounded Induced Matching Treewidth

SIAM Journal on Discrete Mathematics
For a tree decomposition $\mathcal{T}$ of a graph $G$, let $\mu(\mathcal{T})$ denote the maximum size of an induced matching in $G$ with the property that some bag of $\mathcal{T}$ contains at least one endpoint of every edge of the matching. The induced
Tara Abrishami, Marcin Bria'nski, Jadwiga Czyzewska, Rose McCarty, Martin Milanič, Paweł Rzaͅżewski, Bartosz Walczak   +6 more
semanticscholar   +1 more source

Bounding the Treewidth of Outer k-Planar Graphs via Triangulations

International Symposium Graph Drawing and Network Visualization
The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in terms of the treewidth. In this paper, we study the treewidth of outer $k$-planar graphs, that is, graphs that
Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, Alexander Wolff   +4 more
semanticscholar   +1 more source

Sparse Induced Subgraphs of Large Treewidth

J. Comb. Theory B
Motivated by an induced counterpart of treewidth sparsifiers (i.e., sparse subgraphs keeping the treewidth large) provided by the celebrated Grid Minor theorem of Robertson and Seymour [JCTB '86] or by a classic result of Chekuri and Chuzhoy [SODA '15 ...
Édouard Bonnet
semanticscholar   +1 more source

Treewidth of Graphs

2014
• O.k p log k/. • For all {v;w} 2 E, there is an i 2 I with v, w 2 Xi . • For all v 2 V , the set {i 2 I jv 2 Xi} induces a connected subtree of T . The width of a tree decomposition is max i2I jXi j 1, and the treewidth of a graph G is the minimum width of a tree decomposition of G (Fig. 1). An alternative definition is in terms of chordal graphs.
openaire   +5 more sources