Copertina

Treewidth Inapproximability and Tight ETH Lower Bound

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Bonnet, Édouard
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics 68Q17 F.2.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Answering Related Questions
di: Bonnet, Édouard
Pubblicazione: (2025)

Coloring Hardness on Low Twin-Width Graphs
di: Bonnet, Édouard
Pubblicazione: (2025)

Mim-Width is paraNP-complete
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
di: Chen, Yijia, et al.
Pubblicazione: (2023)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
di: Philip, Geevarghese, et al.
Pubblicazione: (2026)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

Induced Disjoint Paths Without an Induced Minor
di: Aboulker, Pierre, et al.
Pubblicazione: (2025)

Sparse Induced Subgraphs of Large Treewidth
di: Bonnet, Édouard
Pubblicazione: (2024)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
di: Liao, Chao, et al.
Pubblicazione: (2022)

Interval Graphs are Reconstructible
di: Heinrich, Irene, et al.
Pubblicazione: (2025)

Symmetric-Difference (Degeneracy) and Signed Tree Models
di: Bonnet, Édouard, et al.
Pubblicazione: (2024)

A New Temporal Interpretation of Cluster Editing
di: Bocci, Cristiano, et al.
Pubblicazione: (2022)

A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs
di: Cook, Linda, et al.
Pubblicazione: (2025)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
di: Demaine, Erik D., et al.
Pubblicazione: (2024)

Pliability and Approximating Max-CSPs
di: Romero, Miguel, et al.
Pubblicazione: (2019)

A Decomposition Approach to the Weighted $k$-server Problem
di: Ayyadevara, Nikhil, et al.
Pubblicazione: (2024)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
di: Bonnet, Édouard, et al.
Pubblicazione: (2023)

Logarithmic Weisfeiler--Leman and Treewidth
di: Levet, Michael, et al.
Pubblicazione: (2023)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
di: Hougardy, Stefan, et al.
Pubblicazione: (2025)

Probabilistic Analysis of Edge Elimination for Euclidean TSP
di: Zhong, Xianghui
Pubblicazione: (2018)

Color-Constrained Arborescences in Edge-Colored Digraphs
di: Ardra, P. S., et al.
Pubblicazione: (2025)

Treedepth Inapproximability and Exponential ETH Lower Bound
di: Bonnet, Édouard, et al.
Pubblicazione: (2025)

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
di: Bonnet, Édouard, et al.
Pubblicazione: (2023)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2024)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
di: Fairbairn, David L., et al.
Pubblicazione: (2024)

Tight Inapproximability of Target Set Reconfiguration
di: Ohsaka, Naoto
Pubblicazione: (2024)

Lower Bounds for Leaf Rank of Leaf Powers
di: Høgemo, Svein
Pubblicazione: (2024)

Computing parameters that generalize interval graphs using restricted modular partitions
di: Bonomo-Braberman, Flavia, et al.
Pubblicazione: (2025)

A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
di: Sun, Hao
Pubblicazione: (2023)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
di: Jansen, Klaus, et al.
Pubblicazione: (2024)

Maximum Matchings in Geometric Intersection Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2019)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
di: Calamoneri, Tiziana, et al.
Pubblicazione: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
di: Calamoneri, Tiziana, et al.
Pubblicazione: (2025)

Graph polynomials: some questions on the edge
di: Farr, Graham, et al.
Pubblicazione: (2024)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
di: Beisegel, Jesse, et al.
Pubblicazione: (2025)

Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
di: Ma, Will, et al.
Pubblicazione: (2024)

Online Bipartite Matching in the Probe-Commit Model
di: Borodin, Allan, et al.
Pubblicazione: (2023)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
di: MacRury, Calum, et al.
Pubblicazione: (2022)

Sublinear-Time Computation in the Presence of Online Erasures
di: Kalemaj, Iden, et al.
Pubblicazione: (2021)

Sum-of-squares lower bounds for Non-Gaussian Component Analysis
di: Diakonikolas, Ilias, et al.
Pubblicazione: (2024)