$r$-Gather Clustering and $r$-Gathering on Spider: FPT Algorithms and Hardness

Soh Kumabe; Takanori Maehara

arxiv: 1907.04088 · v1 · pith:SCRBDES4new · submitted 2019-07-09 · 💻 cs.DS

r-Gather Clustering and r-Gathering on Spider: FPT Algorithms and Hardness

Soh Kumabe , Takanori Maehara This is my paper

Pith reviewed 2026-05-25 00:02 UTC · model grok-4.3

classification 💻 cs.DS

keywords r-gather clusteringr-gatheringspider graphsFPT algorithmsNP-hardnessparameterized complexityclusteringfacility location

0 comments

The pith

The min-max r-gather clustering and r-gathering problems admit FPT algorithms on spiders parametrized by leg count.

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

This paper develops the first fixed-parameter tractable algorithms for dividing points on a spider into clusters of size at least r while minimizing the maximum cluster diameter. It does the same for the variant that also assigns each cluster to a facility to minimize the maximum user-to-facility distance. The parameter used is solely the number of legs in the spider. The work also establishes that both problems are NP-hard on spiders when the leg count is unbounded. A reader would care because these results separate tractable cases from hard ones for location problems on tree-like graphs with a center.

Core claim

We propose the first fixed-parameter tractable (FPT) algorithms for both the min-max r-gather clustering problem and the min-max r-gathering problem on spider graphs, parameterized only by the number of legs. We also prove that these problems are NP-hard when the number of legs is arbitrarily large.

What carries the argument

The spider graph structure, with a central vertex and independent legs, which permits dynamic programming that processes each leg separately while coordinating through the center.

If this is right

When the number of legs is a fixed constant, both problems can be solved in time f(legs) times a polynomial in the number of users and facilities.
The problems remain NP-hard on spiders even when all other parameters such as r are fixed, once the leg count is allowed to grow.
The same FPT approach does not extend directly to arbitrary graphs or to spiders whose leg count is unbounded.

Where Pith is reading between the lines

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

The spider may mark a structural threshold where min-max clustering transitions from FPT to hard under leg parameterization.
Similar leg-based decompositions could yield FPT results for related assignment or covering problems on the same graphs.

Load-bearing premise

The input graph is a spider whose central vertex and leg decomposition are known in advance and can be exploited to decompose the clustering decisions along the legs.

What would settle it

A polynomial-time algorithm for either problem on spider graphs whose leg count is part of the input size, or a concrete spider instance with a small fixed leg count on which the claimed FPT procedure exceeds its stated runtime bound.

read the original abstract

We consider min-max $r$-gather clustering problem and min-max $r$-gathering problem. In the min-max $r$-gather clustering problem, we are given a set of users and divide them into clusters with size at least $r$; the goal is to minimize the maximum diameter of clusters. In the min-max $r$-gathering problem, we are additionally given a set of facilities and assign each cluster to a facility; the goal is to minimize the maximum distance between the users and the assigned facility. In this study, we consider the case that the users and facilities are located on a ``spider'' and propose the first fixed-parameter tractable (FPT) algorithms for both problems, which are parametrized by only the number of legs. Furthermore, we prove that these problems are NP-hard when the number of legs is arbitrarily large.

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

FPT algorithms for the two r-gather problems on spiders via per-leg DP, plus NP-hardness for unbounded legs.

read the letter

The main takeaway is that the paper supplies the first FPT algorithms for min-max r-gather clustering and min-max r-gathering on spiders, with the parameter being only the number of legs, and shows NP-hardness once the leg count is unbounded. The approach rests on the spider decomposition: a center plus independent path legs. Dynamic programming on each leg computes the feasible clusterings or assignments for that leg, then the states are combined at the center. With the leg count as parameter the combination stays FPT, which is the standard route for this graph class and appears to handle the min-max diameter and distance objectives without hidden exponential dependence on r. The hardness result is presented as a separate argument that rules out dropping the parameter. The work is narrow but cleanly executed for its scope. The abstract gives no explicit running times or proof sketches, so the precise polynomial factors per leg and the exact state definitions need verification in the body, but the stress-test note finds no inconsistency in the basic DP plan. This is useful for researchers working on parameterized algorithms for clustering or facility location on trees, spiders, or other low-treewidth graphs with bounded branches. A reader already familiar with DP on paths and spiders will see the value quickly. It deserves a serious referee because the claims are concrete, the structural restriction is used explicitly, and the results are new relative to the cited prior work.

Referee Report

0 major / 2 minor

Summary. The paper considers the min-max r-gather clustering problem (partition users into clusters of size at least r minimizing maximum cluster diameter) and the min-max r-gathering problem (additionally assign clusters to facilities minimizing maximum user-to-facility distance), both with users and facilities on a spider graph. It claims the first FPT algorithms for both problems when parameterized solely by the number of legs, together with NP-hardness proofs when the number of legs is unbounded.

Significance. If correct, the work supplies the first parameterized tractability results for these min-max clustering problems on spiders by exploiting the center-plus-independent-legs decomposition for dynamic programming whose states combine across a parameter-bounded number of legs. The explicit NP-hardness for unbounded legs completes the picture. The manuscript ships explicit algorithmic constructions and a separate hardness proof; these are strengths that should be retained in any revision.

minor comments (2)

The abstract states existence of FPT algorithms but omits the specific running-time expressions (e.g., f(#legs)·n^O(1) form); adding them would improve readability without altering the claims.
Notation for the spider (central vertex, leg count k, leg lengths) should be introduced once in §1 or §2 and used consistently thereafter to avoid minor re-definitions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and the recommendation to accept. No major comments were raised that require addressing.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper claims explicit FPT algorithms for the two min-max problems on spider graphs (parameterized solely by leg count) via per-leg dynamic programming whose states combine across the parameter, plus a separate NP-hardness proof for unbounded legs. No equations, self-definitional constructions, fitted inputs renamed as predictions, or load-bearing self-citations appear in the provided claims or abstract. The spider decomposition is a standard structural restriction that directly enables the DP without reducing the central result to its own inputs by construction. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract; the contribution is stated purely in terms of algorithmic existence and complexity classification on a given graph class.

pith-pipeline@v0.9.0 · 5682 in / 1198 out tokens · 24452 ms · 2026-05-25T00:02:37.353979+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We propose the first fixed-parameter tractable (FPT) algorithms for both problems, which are parametrized by only the number of legs... NP-hard when the number of legs is arbitrarily large.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 4... suffix-special family of multi-leg clusters... DP[i][S][j][k]

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.