Buchumschlag

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Frei, Fabian, Ghazy, Ahmed, Hartmann, Tim A., Hörsch, Florian, Marx, Dániel
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
von: S., Karthik C., et al.
Veröffentlicht: (2024)

Generalized Graph Packing Problems Parameterized by Treewidth
von: Esmer, Barış Can, et al.
Veröffentlicht: (2025)

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

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

Parameterized Complexity of Vehicle Routing
von: Döring, Michelle, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Odd Coloring
von: Bhyravarapu, Sriram, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Min-Sum-Radii
von: Kumar, Pankaj, et al.
Veröffentlicht: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

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

Inapproximability of Maximum Diameter Clustering for Few Clusters
von: Fleischmann, Henry, et al.
Veröffentlicht: (2023)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
von: Bai, Tian, et al.
Veröffentlicht: (2026)

Superconstant Inapproximability of Decision Tree Learning
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Tight Inapproximability of Target Set Reconfiguration
von: Ohsaka, Naoto
Veröffentlicht: (2024)

Removable Online Knapsack and Advice
von: Böckenhauer, Hans-Joachim, et al.
Veröffentlicht: (2020)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2026)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
von: Dey, Palash, et al.
Veröffentlicht: (2026)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

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

Parameterized Vertex Integrity Revisited
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2024)

Parameterized complexity of reconfiguration of atoms
von: Cooper, Alexandre, et al.
Veröffentlicht: (2021)

Parameterized Restless Temporal Path
von: Cauvi, Justine, et al.
Veröffentlicht: (2025)

Parameterized Capacitated Vertex Cover Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2026)

The Parameterized Landscape of Labeled Graph Contractions
von: Lafond, Manuel, et al.
Veröffentlicht: (2025)

Structural Parameterizations for Induced and Acyclic Matching
von: Lampis, Michael, et al.
Veröffentlicht: (2025)

Parameterized Maximum Node-Disjoint Paths
von: Lampis, Michael, et al.
Veröffentlicht: (2024)

Parameterized Critical Node Cut Revisited
von: Knop, Dušan, et al.
Veröffentlicht: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
von: S., Karthik C., et al.
Veröffentlicht: (2023)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

Bandwidth Parameterized by Cluster Vertex Deletion Number
von: Gima, Tatsuya, et al.
Veröffentlicht: (2023)

Parameterized Max Min Feedback Vertex Set
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

Parameterized Algorithms for Editing to Uniform Cluster Graph
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2024)

Structural Parameterizations for Two Bounded Degree Problems Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

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

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

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