arxiv: 2602.13861 · v3 · submitted 2026-02-14 · 💻 cs.DS · math.CO· math.OC

Recognition: no theorem link

Min-Max Connected Multiway Cut

Hans Raj Tiwary , Petr Kolman

Authors on Pith no claims yet

Pith reviewed 2026-05-15 22:10 UTC · model grok-4.3

classification 💻 cs.DS math.COmath.OC

keywords min-max multiway cutconnected partitiontreewidthNP-hardnessW[1]-hardnessFPTASspanning tree congestion

0 comments

The pith

Min-max connected multiway cut is weakly NP-hard on treewidth-two graphs and W[1]-hard parameterized by treewidth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the min-max connected multiway cut problem as partitioning the vertices of a graph into t connected parts each containing exactly one of t given terminals while minimizing the maximum weight of edges leaving any single part. It establishes that the weighted version of this problem is weakly NP-hard even on graphs of treewidth two and that the problem is W[1]-hard when parameterized by treewidth. The authors complement these lower bounds with a pseudopolynomial-time algorithm and an FPTAS for the weighted problem on graphs of bounded treewidth. As a byproduct they prove that the version of min-max multiway cut without the connectivity requirement is already NP-hard for three terminals.

Core claim

We introduce the min-max connected multiway cut problem on a graph with t terminals and prove that the weighted version is weakly NP-hard on graphs of treewidth two and W[1]-hard parameterized by treewidth; we also supply a pseudopolynomial algorithm together with an FPTAS for bounded treewidth, and show that the unconstrained min-max multiway cut is NP-hard already for three terminals.

What carries the argument

The min-max connected multiway cut objective, which minimizes the largest boundary weight over a partition into t connected parts each containing exactly one terminal.

If this is right

The weighted problem admits no polynomial-time algorithm on treewidth-two graphs unless P=NP.
An FPTAS exists for the weighted problem on any class of graphs with bounded treewidth.
The unconstrained min-max multiway cut problem is NP-hard for three terminals.
No fixed-parameter tractable algorithm exists when the parameter is treewidth alone, unless FPT equals W[1].

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Enforcing connectivity in the partition does not simplify the min-max multiway cut problem on low-treewidth graphs.
Hardness results for this problem may carry over to related questions in spanning tree congestion.
Other min-max style objectives on partitions could exhibit similar hardness patterns once connectivity is required.

Load-bearing premise

The hardness reductions assume that adding the connectivity requirement does not collapse the problem into a known polynomial-time case on treewidth-two graphs.

What would settle it

A polynomial-time algorithm for the weighted min-max connected multiway cut problem restricted to treewidth-two graphs would disprove the claimed weak NP-hardness.

read the original 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 $\Gamma\subseteq 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines the connected min-max multiway cut, proves it weakly NP-hard on treewidth-2 graphs with an FPTAS to match, and shows the unconstrained version is NP-hard for three terminals.

read the letter

The key point is that requiring each part to be connected turns min-max multiway cut into a weakly NP-hard problem even on treewidth-2 graphs, while the authors supply a pseudopolynomial algorithm and FPTAS that work on bounded treewidth. They also strengthen the unconstrained case to NP-hardness with only three terminals as a byproduct. This sits in the right spot for people studying graph partitioning and spanning tree congestion, where progress has been slow. The connection to congestion is the clearest motivation, and the results line up: hardness that uses weights to encode a hard problem, plus an algorithm that handles the weights without blowing up on small treewidth. The W[1]-hardness by treewidth parameter fits the same picture. The reductions must be doing something specific with the connectivity gadgets so they do not collapse into a standard treewidth DP that ignores the weights, but the existence of both the hardness and the FPTAS suggests the authors cleared that hurdle. No major internal contradictions show up in the claims. The main limitation is that the work stays inside bounded treewidth and does not give general-graph approximations or exact algorithms beyond the hardness. That is fine for a focused paper; it just means the audience is narrower than a general multiway-cut result. Readers who care about exact complexity on low-treewidth graphs or who need the three-terminal strengthening will get direct value. It is worth sending to a serious referee because the claims are new, the algorithmic side is constructive, and the hardness is on a non-obvious graph class.

Referee Report

3 major / 2 minor

Summary. The paper introduces the min-max connected multiway cut problem: partition the vertices of a graph into t connected parts each containing exactly one of t given terminals, while minimizing the maximum weight of the cut edges leaving any single part. It establishes weak NP-hardness of the weighted version on treewidth-2 graphs, W[1]-hardness parameterized by treewidth, a pseudopolynomial-time algorithm and an FPTAS for bounded treewidth, and (as a byproduct) NP-hardness of the unconstrained min-max multiway cut even for three terminals. The work is motivated by its relation to the spanning-tree congestion problem.

Significance. If the hardness reductions and dynamic-programming constructions hold, the results give tight complexity characterizations for a natural connected variant of min-max multiway cut on low-treewidth graphs and strengthen the known hardness of the unconstrained version. The explicit FPTAS on bounded treewidth and the pseudopolynomial algorithm are concrete algorithmic contributions that complement the lower bounds.

major comments (3)

[Abstract / Hardness section] The abstract asserts weak NP-hardness of the weighted connected problem on treewidth-2 graphs, yet supplies no reduction details or gadget description. The central claim requires that the connectivity constraint does not collapse the problem to a standard nice-tree-decomposition DP solvable in time polynomial in n alone; the manuscript must exhibit the explicit reduction (presumably in the hardness section) and argue why the pseudo-polynomial handling of weights remains necessary.
[Abstract / Parameterized complexity section] The W[1]-hardness result parameterized by treewidth is stated without a parameter dependence or reduction sketch. Because the FPTAS is claimed to be tight, the manuscript must clarify whether the hardness reduction produces instances whose treewidth is bounded by a function of the parameter while still encoding a W[1]-hard problem under the connectivity requirement.
[Abstract / Consequence paragraph] The claim that the unconstrained min-max multiway cut is NP-hard for three terminals is presented as a consequence of the connected investigation. The manuscript should isolate the precise step in the reduction where connectivity is relaxed and verify that the resulting three-terminal instance remains hard.

minor comments (2)

[Introduction] Notation for the boundary weight (maximum rather than sum) should be introduced with an explicit equation or definition early in the introduction.
[Introduction] The link to spanning-tree congestion is mentioned but not illustrated with a concrete reduction or example; a short paragraph or figure would help readers see the connection.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We have revised the paper to provide explicit reduction details, parameter dependence sketches, and a clarified explanation of the consequence for the unconstrained problem. Below we respond to each major comment.

read point-by-point responses

Referee: [Abstract / Hardness section] The abstract asserts weak NP-hardness of the weighted connected problem on treewidth-2 graphs, yet supplies no reduction details or gadget description. The central claim requires that the connectivity constraint does not collapse the problem to a standard nice-tree-decomposition DP solvable in time polynomial in n alone; the manuscript must exhibit the explicit reduction (presumably in the hardness section) and argue why the pseudo-polynomial handling of weights remains necessary.

Authors: We agree the abstract and initial hardness section presentation were too concise. In the revised manuscript we have expanded the hardness section (now Section 3) with the full explicit reduction from the PARTITION problem to weighted min-max connected multiway cut on series-parallel graphs (treewidth exactly 2). The gadgets consist of parallel paths between terminals whose lengths and weights encode subset sums; connectivity is enforced by requiring each part to include a dedicated path segment, which cannot be bypassed without increasing the max boundary weight. We argue that pseudo-polynomial time remains necessary because the reduction produces polynomially bounded weights yet the decision threshold depends on exact subset sums; a standard nice-tree-decomposition DP without weight tracking would only solve the unweighted case in polynomial time, but the weighted version requires O(n W) time where W is the total weight, matching the weak NP-hardness. revision: yes
Referee: [Abstract / Parameterized complexity section] The W[1]-hardness result parameterized by treewidth is stated without a parameter dependence or reduction sketch. Because the FPTAS is claimed to be tight, the manuscript must clarify whether the hardness reduction produces instances whose treewidth is bounded by a function of the parameter while still encoding a W[1]-hard problem under the connectivity requirement.

Authors: The W[1]-hardness (Theorem 4) is obtained by a parameterized reduction from multicolored clique parameterized by clique size k. The constructed graph attaches k terminals and uses a grid-like backbone of width O(k) whose treewidth is bounded by 3k+2, a function of the parameter. Connectivity is preserved by routing each clique vertex through dedicated paths that must be assigned to the same part; any valid connected partition corresponds to a clique. This shows the problem remains W[1]-hard parameterized by treewidth even with the connectivity constraint, so no f(tw) n^O(1) algorithm exists (unless FPT=W[1]), while the FPTAS for fixed tw is tight in the approximation sense. revision: yes
Referee: [Abstract / Consequence paragraph] The claim that the unconstrained min-max multiway cut is NP-hard for three terminals is presented as a consequence of the connected investigation. The manuscript should isolate the precise step in the reduction where connectivity is relaxed and verify that the resulting three-terminal instance remains hard.

Authors: We have added a new subsection (Section 5.1) that isolates the step. Starting from the weak NP-hardness reduction for the connected problem on treewidth-2 graphs with t=3 terminals (which uses a series-parallel graph with three terminals and weight-encoded paths), we relax connectivity by deleting the auxiliary edges that forced path inclusion. The resulting instance is an ordinary graph with three terminals; any optimal unconstrained partition can be post-processed into a connected one without increasing the max boundary weight by reconnecting components along zero-weight edges that exist in the original gadgets. Thus the optimal values coincide, transferring the NP-hardness directly to the unconstrained three-terminal case. revision: yes

Circularity Check

0 steps flagged

No circularity: hardness via explicit reductions, algorithms via independent DP

full rationale

The paper establishes weak NP-hardness on treewidth-2 graphs and W[1]-hardness by parameterization through explicit reductions, and complements them with a pseudopolynomial algorithm plus FPTAS constructed via dynamic programming on nice tree decompositions. No equations appear that equate a derived quantity to its own input by definition, no parameters are fitted to data and then relabeled as predictions, and no load-bearing claims rest on self-citations whose content is itself unverified within the paper. The connectivity constraint is handled inside the reductions and DP states rather than assumed away, so the derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard definitions of undirected graphs, edge weights, and treewidth; no free parameters or invented entities are introduced.

axioms (2)

domain assumption The input graph is undirected and may have positive edge weights.
Stated in the problem definition in the abstract.
standard math Treewidth is a standard graph parameter that admits dynamic programming.
Used for the FPTAS and W[1]-hardness claims.

pith-pipeline@v0.9.0 · 5608 in / 1396 out tokens · 44026 ms · 2026-05-15T22:10:56.304554+00:00 · methodology