Copertina

A tight quasi-polynomial bound for Global Label Min-Cut

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Jaffke, Lars, Lima, Paloma T., Masařík, Tomáš, Pilipczuk, Marcin, Souza, Ueverton S.
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
di: Hatzel, Meike, et al.
Pubblicazione: (2022)

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
di: Jaffke, Lars, et al.
Pubblicazione: (2025)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
di: Kratochvíl, Jan, et al.
Pubblicazione: (2020)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)

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

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

Colouring $(P_r+P_s)$-Free Graphs
di: Klimošová, Tereza, et al.
Pubblicazione: (2018)

On weighted graph separation problems and flow-augmentation
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)

On the Parameterized Complexity of Min-Sum-Radii
di: Kumar, Pankaj, et al.
Pubblicazione: (2026)

Parameterized Max Min Feedback Vertex Set
di: Lampis, Michael, et al.
Pubblicazione: (2023)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
di: Bhaskar, Umang, et al.
Pubblicazione: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
di: Jansen, Bart M. P., et al.
Pubblicazione: (2026)

Minimum Stable Cut and Treewidth
di: Lampis, Michael
Pubblicazione: (2021)

Pseudodeterministic Algorithms for Minimum Cut Problems
di: Agarwala, Aryan, et al.
Pubblicazione: (2025)

Parameterized Critical Node Cut Revisited
di: Knop, Dušan, et al.
Pubblicazione: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

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

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
di: Kenig, Batya
Pubblicazione: (2025)

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

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

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

Revisiting Tree Canonization using polynomials
di: Arvind, V., et al.
Pubblicazione: (2024)

Testing noisy low-degree polynomials for sparsity
di: Bao, Yiqiao, et al.
Pubblicazione: (2025)

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

Hedonic Seat Arrangement Problems
di: Bodlaender, Hans L., et al.
Pubblicazione: (2020)

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

The Parameterized Landscape of Labeled Graph Contractions
di: Lafond, Manuel, et al.
Pubblicazione: (2025)

Parameterized Complexity of MinCSP over the Point Algebra
di: Osipov, George, et al.
Pubblicazione: (2023)

Downward self-reducibility in the total function polynomial hierarchy
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
di: Rohwedder, Lars, et al.
Pubblicazione: (2024)

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

Constant congestion linkages in polynomially strong digraphs in polynomial time
di: Lopes, Raul, et al.
Pubblicazione: (2024)

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

Precoloring extension with demands on paths
di: Das, Arun Kumar, et al.
Pubblicazione: (2025)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
di: Johnson, Matthew, et al.
Pubblicazione: (2022)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
di: Masařík, Tomáš, et al.
Pubblicazione: (2025)

A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
di: Czyżewska, Jadwiga, et al.
Pubblicazione: (2025)

Max-Cut with $ε$-Accurate Predictions
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2024)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)