Cover Image

Minimum Stable Cut and Treewidth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Lampis, Michael
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

Core Stability in Additively Separable Hedonic Games of Low Treewidth
by: Hanaka, Tesshu, et al.
Published: (2024)

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

The Primal Pathwidth SETH
by: Lampis, Michael
Published: (2024)

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

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

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

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

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

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

Parameterized Capacitated Vertex Cover Revisited
by: Lampis, Michael, et al.
Published: (2026)

Structural Parameterizations for Induced and Acyclic Matching
by: Lampis, Michael, et al.
Published: (2025)

Parameterized Maximum Node-Disjoint Paths
by: Lampis, Michael, et al.
Published: (2024)

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

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

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

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

Parameterized Vertex Integrity Revisited
by: Hanaka, Tesshu, et al.
Published: (2024)

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

First Order Logic on Pathwidth Revisited Again
by: Lampis, Michael
Published: (2022)

Structural Parameters for Steiner Orientation
by: Hanaka, Tesshu, et al.
Published: (2025)

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

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
by: Bilò, Davide, et al.
Published: (2024)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
by: Upirvitskiy, Aleksey, et al.
Published: (2026)

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

Fine-grained Meta-Theorems for Vertex Integrity
by: Lampis, Michael, et al.
Published: (2021)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
by: Vroon, Mats, et al.
Published: (2025)

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

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

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

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

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
by: Stoian, Mihail
Published: (2024)

Broadcasting under Structural Restrictions
by: Egami, Yudai, et al.
Published: (2025)

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

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

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

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
by: Beisegel, Jesse, et al.
Published: (2025)

Finding Minimum Distance Preservers: A Parameterized Study
by: Simonov, Kirill, et al.
Published: (2026)

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

Satisfactory Budget Division
by: Gourvès, Laurent, et al.
Published: (2025)