Imagen de Portada

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Esmer, Barış Can, Focke, Jacob, Marx, Dániel, Rzążewski, Paweł
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
por: Esmer, Barış Can, et al.
Publicado: (2022)

Generalized Graph Packing Problems Parameterized by Treewidth
por: Esmer, Barış Can, et al.
Publicado: (2025)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
por: Focke, Jacob, et al.
Publicado: (2022)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
por: Focke, Jacob, et al.
Publicado: (2023)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
por: Greilhuber, Jakob, et al.
Publicado: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
por: Esmer, Barış Can, et al.
Publicado: (2022)

Residue Domination in Bounded-Treewidth Graphs
por: Greilhuber, Jakob, et al.
Publicado: (2024)

k-SUM Hardness Implies Treewidth-SETH
por: Lampis, Michael
Publicado: (2025)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
por: Döring, Simon, et al.
Publicado: (2024)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
por: Dvořák, Pavel, et al.
Publicado: (2022)

Can You Link Up With Treewidth?
por: Curticapean, Radu, et al.
Publicado: (2024)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
por: Chudigiewitsch, Florian, et al.
Publicado: (2026)

Minimum Stable Cut and Treewidth
por: Lampis, Michael
Publicado: (2021)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
por: Bhore, Sujoy, et al.
Publicado: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
por: Foucaud, Florent, et al.
Publicado: (2023)

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
por: Ganian, Robert, et al.
Publicado: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
por: Guruswami, Venkatesan, et al.
Publicado: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
por: Kleinberg, Robert, et al.
Publicado: (2026)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
por: Esmer, Barış Can, et al.
Publicado: (2024)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
por: Lokshtanov, Daniel, et al.
Publicado: (2024)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
por: Chu, Huairui, et al.
Publicado: (2023)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
por: Adriaens, Florian, et al.
Publicado: (2024)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
por: Assadi, Sepehr, et al.
Publicado: (2025)

Structural Parameterizations for Two Bounded Degree Problems Revisited
por: Lampis, Michael, et al.
Publicado: (2023)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
por: Gaikwad, Ajinkya, et al.
Publicado: (2025)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
por: Curticapean, Radu, et al.
Publicado: (2024)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
por: Putterman, Aaron, et al.
Publicado: (2026)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
por: S., Karthik C., et al.
Publicado: (2023)

Neighborhood-Aware Graph Labeling Problem
por: Shahverdikondori, Mohammad, et al.
Publicado: (2026)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
por: Hu, Bingbing, et al.
Publicado: (2024)

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

Self-referential instances of the dominating set problem are irreducible
por: Zhou, Guangyan
Publicado: (2026)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
por: Frei, Fabian, et al.
Publicado: (2024)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
por: Baril, Ambroise, et al.
Publicado: (2025)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
por: Frei, Fabian, et al.
Publicado: (2025)

Improved Hardness-of-Approximation for Token Swapping
por: Hiken, Sam, et al.
Publicado: (2024)

Hardness of Dynamic Core and Truss Decompositions
por: Couto, Yan S., et al.
Publicado: (2025)

Algorithms and Hardness for Estimating Statistical Similarity
por: Bhattacharyya, Arnab, et al.
Publicado: (2025)

Sampling Permutations with Cell Probes is Hard
por: Alekseev, Yaroslav, et al.
Publicado: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
por: Herrmann, Anton, et al.
Publicado: (2025)