Copertina

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Esmer, Barış Can, Focke, Jacob, Marx, Dániel, Rzążewski, Paweł
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
di: Esmer, Barış Can, et al.
Pubblicazione: (2024)

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

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

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

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

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

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

A tight quasi-polynomial bound for Global Label Min-Cut
di: Jaffke, Lars, et al.
Pubblicazione: (2022)

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

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
di: Kluk, Kacper, et al.
Pubblicazione: (2025)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
di: Yang, Yang
Pubblicazione: (2024)

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

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

Nine lower bound conjectures on streaming approximation algorithms for CSPs
di: Singer, Noah G.
Pubblicazione: (2025)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
di: Dumas, Maël, et al.
Pubblicazione: (2022)

A note on approximating the average degree of bounded arboricity graphs
di: Eden, Talya, et al.
Pubblicazione: (2026)

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

Algorithms and complexity for monitoring edge-geodetic sets in graphs
di: Foucaud, Florent, et al.
Pubblicazione: (2024)

The complexity of testing all properties of planar graphs, and the role of isomorphism
di: Basu, Sabyasachi, et al.
Pubblicazione: (2021)

On the complexity of global Roman domination problem in graphs
di: Reddy, Sangam Balchandar, et al.
Pubblicazione: (2026)

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

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

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

The Leafed Induced Subtree in chordal and bounded treewidth graphs
di: Baste, Julien
Pubblicazione: (2023)

Fast and simple multiplication of bounded twin-width matrices
di: Kozma, László, et al.
Pubblicazione: (2026)

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

Clifford testing: algorithms and lower bounds
di: Hinsche, Marcel, et al.
Pubblicazione: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
di: Dell, Holger, et al.
Pubblicazione: (2022)

Optimal lower bounds for quantum state tomography
di: Scharnhorst, Thilo, et al.
Pubblicazione: (2025)

The communication complexity of distributed estimation
di: Gopalan, Parikshit, et al.
Pubblicazione: (2025)

Parameterized complexity of reconfiguration of atoms
di: Cooper, Alexandre, et al.
Pubblicazione: (2021)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
di: Chudnovsky, Maria, et al.
Pubblicazione: (2024)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
di: Bodlaender, Hans L., et al.
Pubblicazione: (2025)

On the complexity and approximability of Bounded access Lempel Ziv coding
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2024)

On girth and the parameterized complexity of token sliding and token jumping
di: Bartier, Valentin, et al.
Pubblicazione: (2020)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
di: Enright, Jessica, et al.
Pubblicazione: (2020)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
di: Michel, Lukas, et al.
Pubblicazione: (2023)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
di: Chakraborty, Dibyayan, et al.
Pubblicazione: (2024)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
di: Ducoffe, Guillaume
Pubblicazione: (2026)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
di: Allcock, Jonathan, et al.
Pubblicazione: (2024)