Pith. sign in

REVIEW 5 minor 29 references

Minimum consistent subsets on weighted graphs of treewidth tw can be found in time 3^{c(tw+1)} n^{tw+O(1)}, and matching ETH lower bounds show this dependence is essentially tight.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 13:34 UTC pith:AKFDYYMB

load-bearing objection Solid fine-grained map for MCS/WMCS: real DP improvement on weighted treewidth plus matching ETH bounds; worth engaging.

arxiv 2607.28240 v1 pith:AKFDYYMB submitted 2026-07-30 cs.DS cs.CC

Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset

Robert Ganian , Manolis Vasilakis , Simon Wietheger This is my paper
classification cs.DS cs.CC MSC 68Q2568Q2705C85
keywords minimum consistent subsettreewidthfine-grained complexityETH lower boundsvertex covertreedepthnearest-neighbor classificationinstance selection
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Nearest-neighbor classification on large labeled data sets is slowed by the need to keep every training point. The classical fix is to keep only a small consistent subset: a set of centers that still correctly labels every point by nearest-neighbor rule. This paper maps exactly how hard that task is once distances come from a graph (weighted or unweighted). The central positive result is a dynamic-programming algorithm that solves the weighted problem on any graph of treewidth tw in time roughly 3^{c·tw} n^{tw}. The same algorithm immediately improves the best previous bound for ordinary trees. Matching lower bounds under the Exponential Time Hypothesis then prove that neither the treewidth exponent nor the color factor can be improved in any substantial way, even on trees or when only two colors are used. A second algorithm reduces the dependence on vertex-cover size from slightly super-exponential to single-exponential. Together the results draw a sharp line between the graph structures on which consistent-subset selection is tractable and those on which it is not.

Core claim

Weighted Minimum Consistent Subset on an n-vertex c-colored graph of treewidth tw can be solved in time 3^{c·(tw+1)}·n^{tw+O(1)}. The same bound specializes to a 9^c n^{O(1)} algorithm on trees, improving the previous 26^c bound, and the exponential dependence on both tw and c is essentially optimal under the ETH.

What carries the argument

Dynamic programming over a nice tree decomposition whose signatures store, for every bag vertex, a promised distance to the global solution together with the set of colors realized at that distance and the subset of those colors already witnessed inside the processed subtree; join nodes are combined by a fast cover-product convolution so that the dependence on the number of colors stays single-exponential.

Load-bearing premise

The matching lower bounds all rest on the Exponential Time Hypothesis that 3-SAT has no 2^{o(n+m)}-time algorithm; if that hypothesis fails the tightness claims collapse while the algorithms remain correct.

What would settle it

An algorithm that solves 2-colored Weighted Minimum Consistent Subset in time n^{o(tw+k)} on graphs of treewidth tw, or a 2^{o(c)} n^{O(1)} algorithm even on trees of bounded depth, would refute the claimed ETH-tightness.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any metric whose distance graph has small treewidth admits a practical consistent-subset algorithm whose cost is exponential only in treewidth and number of classes.
  • The earlier vertex-cover algorithm for unweighted MCS improves from vc^{O(vc)} to single-exponential 5^{vc} n^{O(1)}, matching the ETH lower bound up to the base of the exponential.
  • On graphs of treedepth td the running time becomes 2^{O(td^2+c·td)} n^{O(1)}, and the quadratic dependence on td cannot be removed under ETH.
  • Weighted MCS remains hard even for vertex cover: no f(k+vc) n^{o(k+vc)} algorithm exists under ETH, so the n^{O(vc)} algorithm given in the paper is asymptotically optimal.

Where Pith is reading between the lines

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

  • Because every finite metric is a weighted complete graph, the treewidth algorithm immediately supplies the first non-trivial FPT-style result for consistent-subset selection in arbitrary low-treewidth metrics, not merely graphs.
  • The same signature technique should transfer to related condensation problems (selective subsets, nearest-neighbor condensation) whenever the underlying space admits a tree decomposition of small width.
  • Empirical solvers for instance selection could be stress-tested on random graphs of controlled treewidth to see whether the theoretical 3^{c·tw} barrier appears in practice.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper maps the fine-grained complexity of Minimum Consistent Subset (MCS) and its weighted variant (WMCS) on graphs. The central algorithmic result is a dynamic program over nice tree decompositions that solves WMCS in time 3^{c·(tw+1)}·n^{tw+O(1)} (Theorem 1), by storing global distance/color promises per bag vertex and combining join nodes via fast cover products. This immediately improves the prior 26^c n^{O(1)} bound for unweighted MCS on trees to 9^c n^{O(1)} and yields a 2^{O(td^2+c·td)} n^{O(1)} algorithm parameterized by treedepth. Matching ETH lower bounds rule out n^{o(tw+k)} (even for c=2 and pathwidth/fvs), 2^{o(c)} n^{O(1)} on bounded-depth trees, and 2^{o(td^2)} n^{O(1)}. The paper further improves the recent vc^{O(vc)} n^{O(1)} MCS algorithm to single-exponential 5^{vc} n^{O(1)} and gives an n^{O(vc)} algorithm for WMCS.

Significance. The work cleanly delineates the tractability boundary of consistent-subset selection under standard structural parameters for both weighted and unweighted metrics. Theorem 1 is a genuine advance: it simultaneously generalizes from trees to bounded-treewidth weighted graphs and improves the exponential dependence on the number of colors. The lower-bound suite (especially the multicolored-independent-set reduction of Lemma 6 and the treedepth/3-SAT composition of Theorem 13) is non-trivial and essentially matches the upper bounds under ETH. The single-exponential vertex-cover algorithm (Theorem 21) closes a natural gap left by the AAAI 2026 result. Strengths include fully explicit DP transitions with soundness/completeness claims, standard fast subset-convolution machinery, and self-contained gadget arguments. If the distance-layer arithmetic in the long reductions holds, the paper is a definitive complexity map for the problem.

minor comments (5)
  1. [Section 3] Section 3, signature definition and |Σ_t| bound: the claim |Σ_t| ≤ (k+1)·n^b·3^{c b} is correct, but it would help the reader to state explicitly that k ≤ n is used only later for the join-node polynomial factors, not for the signature count itself.
  2. [Lemma 6] Lemma 6 / Figure 2: the local view is helpful, but several distance expressions (e.g., 3n+6−|σ_i−s|) appear only in the text. A short table of the key distances from each marked vertex to the selected terminals would make the forward and reverse arguments easier to check.
  3. [Theorem 15] Theorem 15 construction: the claim that T has treedepth at most 3 is correct (T−u is a star forest), yet the wrap-up also mentions vertex integrity; a one-sentence clarification that the same construction bounds vertex integrity by 5 would avoid any ambiguity.
  4. [Figure 1] Figure 1 caption and the surrounding paragraph refer to a “mindmap”; the figure is an ordinary parameter-relation diagram. Minor wording polish would suffice.
  5. [References] References: the AAAI 2026 citation is fine for an arXiv preprint, but ensure the final camera-ready entry matches the published proceedings pagination once available.

Circularity Check

0 steps flagged

No significant circularity: self-contained DP algorithms and ETH reductions from external problems

full rationale

This is a fine-grained complexity paper whose positive results are explicit dynamic programs (global distance/color signatures over nice tree decompositions; cover-product join; distance-vector enumeration for vertex cover) and whose negative results are polynomial reductions from Multicolored Independent Set, 3-SAT, Vertex Cover, and Dominating Set under the standard ETH. Nothing is fitted to data and then relabeled a prediction; no quantity is defined in terms of the claim it is said to derive; self-citations point to prior MCS algorithms being improved or to textbook ETH consequences, not to author-only uniqueness theorems that force the present bounds. The derivation chain is therefore independent of its own outputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 2 invented entities

Pure fine-grained complexity paper. Load-bearing external assumptions are ETH and standard structural graph parameters; no empirical free parameters. Technical DP signatures and marked-vertex gadgets are proof devices, not physical entities.

axioms (5)
  • domain assumption Exponential Time Hypothesis: 3-SAT on n variables and m clauses has no 2^{o(n+m)}-time algorithm.
    Invoked for all lower bounds (Section 2; Theorems 12–15, 14).
  • domain assumption Multicolored Independent Set has no f(q) n^{o(q)} algorithm under ETH.
    Starting point of Lemma 6 and Theorems 12–14; cited from Cygan et al. parameterized-algorithms monograph.
  • standard math Standard definitions and separation properties of nice tree decompositions, pathwidth, treedepth, and vertex cover.
    Section 2; used throughout the DP and parameter bounds.
  • standard math Floyd–Warshall / Dijkstra correctly compute all-pairs or cover-to-vertex distances on positive edge weights.
    Preprocessing step of Theorem 1 and Lemma 16.
  • standard math Fast cover product of subset tables can be evaluated in 2^{|Ω|} |Ω|^{O(1)} time.
    Claim 4 cites Cygan et al., Theorem 10.14, for join-node combination.
invented entities (2)
  • DP signature (s, (f_i), (R_i), (C_i)) with global distance/color promises no independent evidence
    purpose: State of the treewidth DP that allows forgetting vertices whose witnesses lie outside the subtree.
    Defined in Section 3; purely algorithmic bookkeeping with no claim of external existence.
  • Marked-vertex forcing gadget (two-level leaves) no independent evidence
    purpose: Force both colors at minimum distance in the ETH reductions without selecting the marked vertex.
    Construction device in Lemma 6 / Theorem 12; not an ontological claim.

pith-pipeline@v1.2.0-daily-grok45 · 33995 in / 2766 out tokens · 54017 ms · 2026-07-31T13:34:43.671457+00:00 · methodology

0 comments
read the original abstract

Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretical formulation of this objective is the Minimum Consistent Subset (MCS) problem. While recent research has explored its complexity on unweighted graphs to uncover structural boundaries of tractability, arbitrary metric spaces are much more accurately modeled by (edge-)weighted graphs. In this paper, we develop a comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs. As our main result, we introduce a $3^{c \cdot(\mathrm{tw}+1)}\cdot n^{\mathrm{tw}+\mathcal{O}(1)}$ algorithm for $n$-vertex $c$-colored MCS instances on weighted graphs of treewidth $\mathrm{tw}$, substantially improving upon the previous state-of-the-art algorithm for unweighted MCS on trees both in terms of generality and running time. We complement this positive result with a series of lower bounds that rule out asymptotic improvements to the running time for both weighted and unweighted graphs under the Exponential Time Hypothesis (ETH). Moreover, we improve the recent slightly superexponential vertex-cover based algorithm for unweighted MCS (AAAI 2026) to a single-exponential one, and rule out further improvements to subexponential running times under the ETH. Together, our results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.

Figures

Figures reproduced from arXiv: 2607.28240 by Manolis Vasilakis, Robert Ganian, Simon Wietheger.

Figure 1
Figure 1. Figure 1: An overview of the relations between our algorithms and lower bounds; the latter assume [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A local view of the construction in Theorem 12 for a single conflicting pair [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Local view on the construction for the reduction in Theorem 14: two selection gadgets [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Part of the construction in the proof of Theorem 15. Squared vertices are selected. [PITH_FULL_IMAGE:figures/full_fig_p022_4.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 13 canonical work pages

  1. [1]

    Complexity of finding embeddings in a k-tree.SIAM Journal on Algebraic Discrete Methods, 8(2):277–284, 1987.doi:10.1137/ 0608024

    Stefan Arnborg, Derek G Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree.SIAM Journal on Algebraic Discrete Methods, 8(2):277–284, 1987.doi:10.1137/ 0608024

    1987

  2. [2]

    Nandy, Krishna Priya K

    Aritra Banik, Sayani Das, Anil Maheshwari, Bubai Manna, Subhas C. Nandy, Krishna Priya K. M., Bodhayan Roy, Sasanka Roy, and Abhishek Sahu. Minimum consistent subset in trees and interval graphs. InFSTTCS 2024, volume 323 ofLIPIcs, pages 7:1–7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.doi:10.4230/LIPICS.FSTTCS.2024.7

    work page doi:10.4230/lipics.fsttcs.2024.7 2024

  3. [3]

    Learning with structure: Computing consistent subsets on structurally-regular graphs

    Aritra Banik, Mano Prakash Parthasarathi, Venkatesh Raman, Diya Roy, and Abhishek Sahu. Learning with structure: Computing consistent subsets on structurally-regular graphs. In AAAI 2026, pages 14149–14156. AAAI Press, 2026.doi:10.1609/AAAI.V40I17.38427

    work page doi:10.1609/aaai.v40i17.38427 2026

  4. [4]

    Computational social choice: Parameterized complexity and challenges.Comput

    Jiehua Chen, Christian Hatschka, and Sofia Simola. Computational social choice: Parameterized complexity and challenges.Comput. Sci. Rev., 61:100835, 2026.doi:10.1016/J.COSREV.2025. 100835

    doi:10.1016/j.cosrev.2025 2026

  5. [5]

    Refined lower bounds for nearest neighbor condensation

    Rajesh Chitnis. Refined lower bounds for nearest neighbor condensation. InInternational Conference on Algorithmic Learning Theory, Proceedings of Machine Learning Research, pages 262–281. PMLR, 2022. URL:https://proceedings.mlr.press/v167/chitnis22a.html

    2022

  6. [6]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3

    doi:10.1007/978-3-319-21275-3 2015

  7. [7]

    Sanjana Dey, Anil Maheshwari, and Subhas C. Nandy. Minimum consistent subset problem for trees. InFCT 2021, Lecture Notes in Computer Science, pages 204–216. Springer, 2021. doi:10.1007/978-3-030-86593-1_14. 30

    work page doi:10.1007/978-3-030-86593-1_14 2021

  8. [8]

    Sanjana Dey, Anil Maheshwari, and Subhas C. Nandy. Minimum consistent subset of simple graph classes.Discret. Appl. Math., 338:255–277, 2023.doi:10.1016/J.DAM.2023.05.024

    work page doi:10.1016/j.dam.2023.05.024 2023

  9. [9]

    Springer, 6 edition, 2025.doi:10.1007/978-3-662-70107-2

    Reinhard Diestel.Graph Theory, volume 173 ofGraduate Texts in Mathematics. Springer, 6 edition, 2025.doi:10.1007/978-3-662-70107-2

    doi:10.1007/978-3-662-70107-2 2025

  10. [10]

    Robert W. Floyd. Algorithm 97: Shortest path.Communications of the ACM, 5(6):345, 1962. doi:10.1145/367766.368168

    arXiv 1962

  11. [11]

    Parameterized complexity in machine learning.Comput

    Robert Ganian. Parameterized complexity in machine learning.Comput. Sci. Rev., 59:100836, 2026.doi:10.1016/J.COSREV.2025.100836

    arXiv 2026

  12. [12]

    The complexity landscape of decompositional parame- ters for ILP.Artif

    Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parame- ters for ILP.Artif. Intell., 257:61–71, 2018.doi:10.1016/J.ARTINT.2017.12.006

    work page doi:10.1016/j.artint.2017.12.006 2018

  13. [13]

    Structural parameterizations of vertex integrity.Theor

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, and Yota Otachi. Structural parameterizations of vertex integrity.Theor. Comput. Sci., 1024:114954, 2025.doi:10.1016/J.TCS.2024.114954

    arXiv 2025

  14. [14]

    Peter E. Hart. The condensed nearest neighbor rule (corresp.).IEEE Trans. Inf. Theory, 14(3):515–516, 1968.doi:10.1109/TIT.1968.1054155

    arXiv 1968

  15. [15]

    Which problems have strongly exponential complexity?J

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity?J. Comput. Syst. Sci., 63(4):512–530, 2001.doi:10.1006/JCSS.2001. 1774

    work page doi:10.1006/jcss.2001 2001

  16. [16]

    GLCC: A general framework for graph-level clustering

    Wei Ju, Yiyang Gu, Binqi Chen, Gongbo Sun, Yifang Qin, Xingyuming Liu, Xiao Luo, and Ming Zhang. GLCC: A general framework for graph-level clustering. In Brian Williams, Yiling Chen, and Jennifer Neville, editors,AAAI 2023, pages 4391–4399. AAAI Press, 2023. doi:10.1609/AAAI.V37I4.25559

    work page doi:10.1609/aaai.v37i4.25559 2023

  17. [17]

    Consistent subset problem with two labels

    Kamyar Khodamoradi, Ramesh Krishnamurti, and Bodhayan Roy. Consistent subset problem with two labels. InCALDAM 2018, Lecture Notes in Computer Science, pages 131–142. Springer, 2018.doi:10.1007/978-3-319-74180-2_11

    work page doi:10.1007/978-3-319-74180-2_11 2018

  18. [18]

    Fine-grained meta-theorems for vertex integrity.Log

    Michael Lampis and Valia Mitsou. Fine-grained meta-theorems for vertex integrity.Log. Methods Comput. Sci., 20(4), 2024.doi:10.46298/LMCS-20(4:18)2024

    work page doi:10.46298/lmcs-20(4:18)2024 2024

  19. [19]

    Interactive deep clustering via value mining

    Honglin Liu, Peng Hu, Changqing Zhang, Yunfan Li, and Xi Peng. Interactive deep clustering via value mining. InNeurIPS 2024, 2024. URL: http://papers.nips.cc/paper_files/ paper/2024/hash/4ac4365b98bc242acd5ab974a05c68a8-Abstract-Conference.html

    2024

  20. [20]

    Lower bounds based on the exponential time hypothesis.Bull

    Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis.Bull. EATCS, 105:41–72, 2011. URL: http://eatcs.org/beatcs/index. php/beatcs/article/view/92

    2011

  21. [21]

    Minimum selective subset on some graph classes

    Bubai Manna. Minimum selective subset on some graph classes. InProceedings of the 37th Canadian Conference on Computational Geometry (CCCG 2025), pages 299–305, 2025

    2025

  22. [22]

    Minimum selective subset on unit disk graphs and circle graphs

    Bubai Manna. Minimum selective subset on unit disk graphs and circle graphs. InCALDAM 2026, Lecture Notes in Computer Science, pages 307–320. Springer, 2026. doi:10.1007/ 978-3-032-17156-6_23. 31

    2026

  23. [23]

    Computing treedepth in polynomial space and linear FPT time

    Wojciech Nadara, Michal Pilipczuk, and Marcin Smulewicz. Computing treedepth in polynomial space and linear FPT time. In30th Annual European Symposium on Algorithms, ESA 2022, volume 244 ofLIPIcs, pages 79:1–79:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.doi:10.4230/LIPICS.ESA.2022.79

    work page doi:10.4230/lipics.esa.2022.79 2022

  24. [24]

    Springer, 2012

    Jaroslav Nesetril and Patrice Ossona de Mendez.Sparsity - Graphs, Structures, and Al- gorithms, volume 28 ofAlgorithms and combinatorics. Springer, 2012. doi:10.1007/ 978-3-642-27875-4

    2012

  25. [25]

    Neil Robertson and Paul D. Seymour. Graph minors. III. planar tree-width.J. Comb. Theory B, 36(1):49–64, 1984.doi:10.1016/0095-8956(84)90013-3

    doi:10.1016/0095-8956(84)90013-3 1984

  26. [26]

    A theorem on boolean matrices.Journal of the ACM, 9(1):11–12, 1962

    Stephen Warshall. A theorem on boolean matrices.Journal of the ACM, 9(1):11–12, 1962. doi:10.1145/321105.321107

    arXiv 1962

  27. [27]

    Gordon T. Wilfong. Nearest neighbor problems.Int. J. Comput. Geom. Appl., 2(4):383–416, 1992.doi:10.1142/S0218195992000226

    work page doi:10.1142/s0218195992000226 1992

  28. [28]

    Semi-supervised clustering framework for fine-grained scene graph generation

    Jiarui Yang, Chuan Wang, Jun Zhang, Shuyi Wu, Jinjing Zhao, Zeming Liu, and Liang Yang. Semi-supervised clustering framework for fine-grained scene graph generation. InAAAI 2025, pages 9220–9228. AAAI Press, 2025.doi:10.1609/AAAI.V39I9.32998

    work page doi:10.1609/aaai.v39i9.32998 2025

  29. [29]

    Aligning contrastive multiple clusterings with user interests

    Shan Zhang, Liangrui Ren, Jun Wang, Yanyu Xu, Carlotta Domeniconi, and Guoxian Yu. Aligning contrastive multiple clusterings with user interests. InIJCAI 2025, pages 7011–7019. ijcai.org, 2025.doi:10.24963/IJCAI.2025/780. 32

    work page doi:10.24963/ijcai.2025/780 2025