Cover Image

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Johnson, Matthew, Martin, Barnaby, Smith, Siani, Pandey, Sukanya, Paulusma, Daniel, van Leeuwen, Erik Jan
Format:	Preprint
Published:	2022
Subjects:	Computational Complexity Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
by: Lucke, Felicia, et al.
Published: (2024)

Computing Subset Vertex Covers in $H$-Free Graphs
by: Brettell, Nick, et al.
Published: (2023)

Planar Multiway Cut with Terminals on Few Faces
by: Pandey, Sukanya, et al.
Published: (2025)

Finding $d$-Cuts in Probe $H$-Free Graphs
by: Dabrowski, Konrad K., et al.
Published: (2025)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)

Steiner Forest for $H$-Subgraph-Free Graphs
by: Eagling-Vose, Tala, et al.
Published: (2026)

The Complexity of Diameter on H-free graphs
by: Oostveen, Jelle J., et al.
Published: (2024)

Parameterized Complexity of Streaming Diameter and Connectivity Problems
by: Oostveen, Jelle J., et al.
Published: (2022)

Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
by: Eagling-Vose, Tala, et al.
Published: (2025)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
by: Hamm, Thekla, et al.
Published: (2026)

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

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

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Colouring Probe $H$-Free Graphs
by: Paulusma, Daniël, et al.
Published: (2025)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
by: Lill, Jonas, et al.
Published: (2024)

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs
by: Lozin, Vadim, et al.
Published: (2022)

Finding d-Cuts in Claw-free Graphs
by: Ahn, Jungho, et al.
Published: (2025)

Solving Problems on Generalized Convex Graphs via Mim-Width
by: Bonomo-Braberman, Flavia, et al.
Published: (2020)

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

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
by: Ahn, Jungho, et al.
Published: (2026)

Graph Classes Closed under Self-intersection
by: Dabrowski, Konrad K., et al.
Published: (2025)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
by: Dorfer, Joseph
Published: (2026)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

$O(n +f(k))$: Truly Linear FPT
by: Bumpus, Benjamin Merlin, et al.
Published: (2026)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

Channel allocation revisited through 1-extendability of graphs
by: Busson, Anthony, et al.
Published: (2024)

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

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
by: Kutner, David C., et al.
Published: (2025)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
by: Hellmuth, Marc, et al.
Published: (2023)

Counting Locally Optimal Tours in the TSP
by: Manthey, Bodo, et al.
Published: (2024)

Exact Algorithms for Edge Deletion to Cactus
by: Akhtar, Sheikh Shakil, et al.
Published: (2026)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

Quantum Approaches to the Minimum Edge Multiway Cut Problem
by: Abbassi, Ali, et al.
Published: (2026)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

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

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
by: Le, Hoang-Oanh, et al.
Published: (2024)

On the Bidirected Cut Relaxation for Steiner Forest
by: Byrka, Jarosław, et al.
Published: (2024)