Image de couverture de livre

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Focke, Jacob, Hörsch, Florian, Li, Shaohua, Marx, Dániel
Format:	Preprint
Publié:	2023
Sujets:	Computational Complexity Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
par: Esmer, Barış Can, et autres
Publié: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
par: Hörsch, Florian, et autres
Publié: (2025)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
par: Focke, Jacob, et autres
Publié: (2022)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
par: Frei, Fabian, et autres
Publié: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
par: Esmer, Barış Can, et autres
Publié: (2022)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
par: Frei, Fabian, et autres
Publié: (2024)

Generalized Graph Packing Problems Parameterized by Treewidth
par: Esmer, Barış Can, et autres
Publié: (2025)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
par: Greilhuber, Jakob, et autres
Publié: (2025)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
par: Chudigiewitsch, Florian, et autres
Publié: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
par: Döring, Simon, et autres
Publié: (2024)

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
par: Caragiannis, Ioannis, et autres
Publié: (2026)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
par: Mu, Ta-Yu, et autres
Publié: (2024)

Complexity of Local Search for Euclidean Clustering Problems
par: Manthey, Bodo, et autres
Publié: (2023)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
par: S., Karthik C., et autres
Publié: (2023)

Neighborhood-Aware Graph Labeling Problem
par: Shahverdikondori, Mohammad, et autres
Publié: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
par: Nederlof, Jesper
Publié: (2026)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Streaming Complexity Separations for Dense and Sparse Graphs
par: Liu, Yang P., et autres
Publié: (2026)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
par: Lehner, Lisa, et autres
Publié: (2025)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
par: Shih, Yu-Sheng, et autres
Publié: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
par: Brânzei, Simina, et autres
Publié: (2026)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
par: Adriaens, Florian, et autres
Publié: (2024)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
par: Zhang, Bingwei, et autres
Publié: (2026)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
par: Assadi, Sepehr, et autres
Publié: (2024)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
par: Firbas, Alexander, et autres
Publié: (2024)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
par: Herrmann, Anton, et autres
Publié: (2025)

On the Space Complexity of Online Convolution
par: Andersson, Joel Daniel, et autres
Publié: (2025)

Kernelization Complexity of Solution Discovery Problems
par: Grobler, Mario, et autres
Publié: (2024)

Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
par: Ruszil, Jakub, et autres
Publié: (2026)

The Query Complexity of Local Search and Brouwer in Rounds
par: Brânzei, Simina, et autres
Publié: (2020)

The Fine-Grained Complexity of Episode Matching
par: Bille, Philip, et autres
Publié: (2021)

Colouring $(P_r+P_s)$-Free Graphs
par: Klimošová, Tereza, et autres
Publié: (2018)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
par: Chen, Xi, et autres
Publié: (2026)

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
par: Holtgrefe, Niels, et autres
Publié: (2026)

Fine-Grained Classification Of Detecting Dominating Patterns
par: Dransfeld, Jonathan, et autres
Publié: (2025)

Scheduling Problems with Constrained Rejections
par: Davies, Sami, et autres
Publié: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2023)

String Consensus Problems with Swaps and Substitutions
par: Gabory, Estéban, et autres
Publié: (2025)

Equivalent Instances for Scheduling and Packing Problems
par: Jansen, Klaus, et autres
Publié: (2025)