Min-Max Connected Multiway Cut

arXiv:2602.13861 · cs.DS, math.CO, math.OC · Submitted 2026-02-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Min-Max Connected Multiway Cut".

Title and authors: Tom: The title itself, Min-Max Connected Multiway Cut, tells you everything about the structure we're dealing with—it’s a multiway cut where connectivity is a requirement for every piece.

Jane: It sounds very specific to the kind of network design or resource allocation problems where you need distinct functional units that are also internally robust.

Lu: The authors are tackling this by looking at different graph structures, specifically focusing on graphs with bounded treewidth, which suggests they're looking for algorithms that work efficiently on structured data.

Meng: Bounded treewidth is good because it often means the problem becomes solvable in time that depends exponentially on the size of that structure, not just the total number of nodes in a huge graph.

Lalam: They actually show an FPT algorithm for this weighted version when you fix how many terminals there are, which means if you only need a few parts, it’s solvable efficiently on trees <ref:2602.13861#pg3>.

The paper's summary: Tom: So the summary of Min-Max Connected Multiway Cut boils down to this: we are looking for a partition where each piece contains one terminal and we minimize the maximum size of its external boundary, with the added rule that every piece must be connected.

Jane: The paper highlights that this combination of constraints—separation and connectivity—is what makes the problem genuinely hard because it's not something you can usually solve by just optimizing for a simple cut objective function.

Lu: They also point out a key connection: this problem is closely linked to the Spanning Tree Congestion problem, which gives them motivation for studying how to tackle these combined requirements together <ref:2602.13861#pg2>.

Meng: From an engineering standpoint, if you're designing a system where you need connected modules but want to minimize the maximum external connection load, this paper tells you that the standard multiway cut approaches might miss that crucial connectivity requirement entirely.

Lalam: They also show that they can solve it in pseudopolynomial time for graphs with bounded treewidth, which is important because pseudopolynomial means the runtime depends on the magnitude of the input numbers rather than just the number of vertices <ref:2602.13861#pg3>.

The paper's improvements: Tom: The authors present a couple of major algorithmic improvements: they give us a pseudopolynomial time algorithm for bounded treewidth graphs, and even better, they provide an FPT algorithm for trees when the number of terminals is fixed.

Jane: That FPT result on trees is pretty significant because it means if your system naturally forms a tree structure, you can solve this optimization problem efficiently as long as you don't have too many parts.

Lu: They also provide an FPTAS for the weighted version on bounded treewidth graphs, which is important because it gives us an approximation scheme that works well even when the numbers are huge.

Meng: For us in production, an FPT algorithm parameterized by terminals means we can handle small numbers of required partitions quickly, which is useful if our system architecture naturally separates into a few main components.

Lalam: They also show that finding an exact solution on trees is NP-hard when the number of terminals isn't fixed, which sets a hard limit on what we can expect for those specific network shapes <ref:2602.13861#pg3>.

Conclusion: Tom: So to wrap up the Min-Max Connected Multiway Cut paper, it shows that while the problem is hard in general, we have efficient solutions on bounded treewidth graphs and FPT solutions for trees when terminals are fixed.

Jane: The main implication for listeners is that when you're designing a system where components need to stay together but you want to control the maximum external load, the structure of your graph—like whether it's a tree or has low treewidth—is crucial to finding a practical solution.

Lu: The paper also points out that there’s still superpolynomial extension complexity for the natural polytope associated with this problem, which suggests that even for well-defined mathematical models, finding good linear programming formulations is still challenging <ref:2602.13861#pg8>.

Meng: For deployment at scale, we need to remember that while we have algorithms for bounded treewidth graphs, they are pseudopolynomial in the input size in unary, so if the graph gets really big quickly, those exact solutions won't run fast enough for real-time decisions.

Lalam: And one limitation the authors flag is that they show NP-hardness even on trees when the number of terminals isn't fixed, so we don't have a guaranteed fast solution there yet <ref:2602.13861#pg3>.

Tom: So in short, this paper gives us tools for structured problems but leaves the general case quite open, with questions about approximation ratios still needing answers <ref:2602.13861#pg17>.

Petr Kolman, Hans Raj Tiwary

Charles University, Faculty of Mathematics and Physics, Department of Applied Mathematics

cs.DS, math.CO, math.OC

Submitted: 2026-02-14

Updated: 2026-11-17

License: http://creativecommons.org/licenses/by/4.0/

The gist: Min-Max Connected Multiway Cut introduces a variant of the multiway cut problem where each part in the partition is required to be connected and seeks to minimize the maximum weight of edges leaving…

Key concepts

Min-Max Connected Multiway Cut
This problem involves dividing a graph into several connected sections, ensuring each section holds one specified terminal. The goal is not to minimize the total boundary weight, but rather to minimize the single largest weight of edges leaving any given section.
Connectivity Constraint
A crucial requirement is that every resulting partition must form a connected subgraph. This means that within each assigned part of the graph, there must be a path between any two vertices in that part, ensuring structural integrity for each segment.
Treewidth
Treewidth measures how 'tree-like' a graph is. Graphs with low treewidth have simple structures, making certain complex optimization problems solvable efficiently using dynamic programming or specialized algorithms. High treewidth indicates more complex, highly interconnected structures.
Extension Complexity
This theoretical tool analyzes the difficulty of finding a solution to an optimization problem by looking at how the size of the input (like the number of vertices) affects the complexity of its associated linear programming formulation. Superpolynomial extension complexity suggests that finding a solution for specific graph structures is inherently hard.

Terminology

Summary

Min-Max Connected Multiway Cut introduces a variant of the multiway cut problem where each part in the partition is required to be connected and seeks to minimize the maximum weight of edges leaving any part (Page 1). p. 0

Where the paper says it

Min-Max Connected Multiway Cut Petr Kolman a u Ȉ Charles University, Faculty of Mathematics and Physics, Department of Applied Mathematics, Czechia Hans Raj Tiwary a u Ȉ Charles University, Faculty of Mathematics and Physics, Department of Applied Mathematics, Czechia Abstract We introduce a variant of the multiway cut that we call the min-max connected multiway cut. Given a graph G = (V, E) and a set Γ ⊆ V of t terminals, partition V into t parts such that each part is connected and contains exactly one terminal; the objective is to minimize the maximum weight of the edges leaving any part of the partition.

This problem is a natural extension of classical problems, combining separation and connectivity constraints, which makes it challenging because little theoretical research has addressed both requirements simultaneously (Page 2). p. 1
Where the paper says it

Though each of the two constraints is relatively wellunderstood individually, and in some cases, the fulfillment of the connectivity requirement comes for free as a bonus of the optimality of the cut objective (see Related Results), the combination of the requirements in the general setting makes the problems challenging. Little theoretical research has addressed both requirements simultaneously.

Problem Definition and Motivation

The Min-Max Connected Multiway Cut problem requires partitioning the vertex set of a graph into parts such that each part is connected and contains exactly one terminal, while minimizing the maximum weight of edges leaving any part (Page 3). This problem differs from the standard multiway cut in two ways: first, the cost is defined as the maximum size of the boundary of any part instead of the sum of all boundaries, and second, each induced subgraph must be connected (Page 3). p. 0

Where the paper says it

Given a graph G = (V, E) and a set Γ ⊆ V of t terminals, partition V into t parts such that each part is connected and contains exactly one terminal; the objective is to minimize the maximum weight of the edges leaving any part of the partition. This problem is a natural modification of the standard multiway cut problem and it differs from it in two ways: first, the cost of a partition is defined to be the maximum size of the boundary of any part, as opposed to the sum of all boundaries, and second, the subgraph induced by each part is required to be connected.

The authors are motivated by its close connection to the Spanning Tree Congestion problem which has been extensively studied but with very little algorithmic progress (Page 2). p. 1
Where the paper says it

Our main motivation for studying the min-max connected multiway cut problem is its close connection to the Spanning Tree Congestion problem (See Sec. 4), a problem that has been studied extensively but with very little algorithmic progress [21].

Hardness Results

The paper presents various hardness results for this problem, including a proof of weak NP-hardness of the weighted version on graphs with treewidth two and W[1]-hardness when parameterized by the treewidth (Page 3). Specifically, they show that the min-max connected multiway cut problem is weakly NP-hard for three terminals on graphs of treewidth three and remains weakly NP-hard on graphs of treewidth two if one allows an arbitrary number of terminals (Page 3). p. 1

Where the paper says it

We also show the same weak NP-hardness for the (unconstrained) min-max multiway cut problem. We show that the min-max connected multiway cut problem remains weakly NP-hard on graphs of treewidth two if one allows arbitrary number of terminals.

Furthermore, they demonstrate that the unconstrained min-max multiway cut problem is NP-hard even for three terminals (Page 3). p. 0
Where the paper says it

Complementing our lower bounds tightly, we also provide a pseudopolynomial time algorithm as well as an FPTAS for the weighted problem on graphs of bounded treewidth. As a consequence of our investigation we also show that the (unconstrained) min-max multiway cut problem is NP-hard even for three terminals, strengthening the known results.

Algorithmic Solutions

The authors provide several algorithmic results depending on the graph structure and weights. For graphs of bounded treewidth, a pseudopolynomial time algorithm is given with running time 2 O(τ 2)N O(τ) where N is the input size in unary (Page 4). p. 2

Where the paper says it

Tiwary XX:3 We give a pseudopolynomial algorithm for the weighted problem on graphs of bounded treewidth. Our algorithm takes time 2 O(τ 2 )N O(τ) where the input size (in unary) is N and the graph has treewidth τ .

Additionally, an FPTAS for the weighted problem on bounded treewidth graphs is provided (Page 4). p. 0
Where the paper says it

We show various hardness results for this problem, including a proof of weak NP-hardness of the weighted version of the problem on graphs with treewidth two, and W[1]-hardness for the problem when parameterized by the treewidth of the graph. Complementing our lower bounds tightly, we also provide a pseudopolynomial time algorithm as well as an FPTAS for the weighted problem on graphs of bounded treewidth.

For trees, the problem is fixed-parameter tractable with respect to the number of terminals (Page 6). p. 2
Where the paper says it

We give an FPTAS for the weighted problem on bounded treewidth graphs. We show that if the number of terminals is fixed, then the weighted problem is polynomial time solvable on trees.

Complexity and Polytope Analysis

The analysis delves into extension complexity, showing that a natural polytope associated with the problem has superpolynomial extension complexity (Page 8). Theorem 10 establishes that for infinitely many integers n, there exists a tree T on n vertices, a set of terminals Γ, and a weight function w on the edges such that the extension complexity of P(T, Γ, w) is superpolynomial in n (Page 9). p. 8

Where the paper says it

◀ ▶ Theorem 10. For infinitely many integers n ∈ N there exists a tree T on n vertices, a set of terminals Γ, and a weight function w on the edges such that the extension complexity of P(T, Γ, w) is superpolynomial in n.

This implies that finding a connected multiway cut of specified size is NP-hard for trees (Page 10). p. 9
Where the paper says it

XX:10 Min-Max Connected Multiway Cut 2. 5 Weighted Exact Min-Max Connected Cut Finally, we show that finding a connected multiway cut of specified size is NP-hard for trees.

Conclusion and Open Problems

The paper concludes by summarizing the complexity landscape, noting that the problem is weakly NP-hard on graphs with treewidth at least two and W[1]-hard when parameterized by the number of terminals (Page 17). A gap remains regarding trees, where only a pseudopolynomial algorithm is known for the weighted problem but its weak NP-hardness status is unknown (Page 17). p. 0

Where the paper says it

We show various hardness results for this problem, including a proof of weak NP-hardness of the weighted version of the problem on graphs with treewidth two, and W[1]-hardness for the problem when parameterized by the treewidth of the graph. Complementing our lower bounds tightly, we also provide a pseudopolynomial time algorithm as well as an FPTAS for the weighted problem on graphs of bounded treewidth.

Another open problem concerns designing an approximation algorithm with a non-trivial ratio and establishing corresponding hardness results for general graphs (Page 17). p. 3
Where the paper says it

XX:4 Min-Max Connected Multiway Cut unique path between u and v in T passes through e; the optimal value for a given graph G is denoted STC(G). The problem was introduced under different names in the late 1990s but till today, the computational complexity of the problem is not much understood: the problem is known to be NP-hard even for graphs of maximum degree at most three [2], there is O ∆ · log3/2 n - approximation algorithm for graphs of maximum degree ∆ [21] but the best known approximation ratio for general graph is n/2 only [25]; interestingly, this is the approximation ratio achieved by any spanning tree.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved analysis of graph partitioning problems by leveraging connectivity constraints, allowing AI systems to solve complex resource allocation and network design tasks where component integrity is critical.

  2. Development of exact solutions for weighted min-max connected multiway cut on graphs of bounded treewidth, enabling precise optimization in structured data environments like VLSI design or power grid management.

  3. Implementation of an FPT algorithm parameterized by the number of terminals for weighted min-max connected multiway cut on trees, allowing efficient solving of routing or connectivity problems in tree-structured networks when the number of required partitions is small.

  4. Application of a pseudopolynomial time algorithm for bounded treewidth graphs to efficiently approximate solutions for large-scale partitioning problems where exact solutions are intractable but high quality approximations are needed.

  5. Integration of techniques from extension complexity theory to design more robust and theoretically grounded linear programming formulations for combinatorial optimization problems related to graph cuts, potentially leading to tighter bounds or better approximation schemes.

Abstract

We introduce a variant of the multiway cut that we call the min-max connected multiway cut. Given a graph G=(V,E) and a set Γ V of t terminals, partition V into t parts such that each part is connected and contains exactly one terminal; the objective is to minimize the maximum weight of the edges leaving any part of the partition. This problem is a natural modification of the standard multiway cut problem and it differs from it in two ways: first, the cost of a partition is defined to be the maximum size of the boundary of any part, as opposed to the sum of all boundaries, and second, the subgraph induced by each part is required to be connected. Although the modified objective function has been considered before in the literature under the name min-max multiway cut, the requirement on each component to be connected has not been studied as far as we know. Our main motivation for studying this problems is its close connection with the spanning tree congestion problem that has been extensively studied but on which little progress has been made. We show various hardness results for this problem, including a proof of weak NP-hardness of the weighted version of the problem on graphs with treewidth two, and W[1] -hardness for the problem when parameterized by the treewidth of the graph. Complementing our lower bounds tightly, we also provide a pseudopolynomial time algorithm as well as an FPTAS for the weighted problem on graphs of bounded treewidth. As a consequence of our investigation we also show that the (unconstrained) min-max multiway cut problem is NP-hard even for three terminals, strengthening the known results.

Sources

Related papers