Pith. sign in

REVIEW 2 minor 31 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

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

T0 review · grok-4.3

If Densest k-Subgraph has no constant-factor approximation then neither does Densest At-Least-k-Subgraph to within 3/2 - ε.

2026-06-29 20:01 UTC pith:5LSGUKI2

load-bearing objection This note gives a simple reduction from DkS to DALkS that yields (3/2-ε) hardness assuming constant-factor DkS hardness, removes the SSE hypothesis for the parameterized (2-ε) case, and adds W[1]-hardness for exact DALkS.

arxiv 2605.25464 v1 pith:5LSGUKI2 submitted 2026-05-25 cs.DS cs.CC

A Note on Approximability of Densest At-Least-k-Subgraph

Bundit Laekhanukit , Pasin Manurangsi , Ohad Trabelsi This is my paper
classification cs.DS cs.CC
keywords Densest k-SubgraphDensest At-Least-k-Subgraphapproximation algorithmsinapproximabilityreductionW[1]-hardnessparameterized complexity
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.

The paper constructs a reduction from Densest k-Subgraph to Densest At-Least-k-Subgraph that carries over inapproximability thresholds. Under the assumption that the exact-k problem has no constant-factor approximation, the at-least-k problem has none better than 3/2 - ε. A stronger hypothesis that Densest k-Subgraph resists approximation to within k to the power 1 minus delta yields 2 - ε hardness for the at-least-k version. Both results apply in the ordinary polynomial-time setting and when parameterized by k. The paper also proves that solving DALkS exactly is W[1]-hard when parameterized by k.

Core claim

A polynomial-time reduction from Densest k-Subgraph to Densest At-Least-k-Subgraph shows that constant-factor inapproximability of the former implies (3/2 - ε)-factor inapproximability of the latter for every ε > 0. The same reduction generalizes under the stronger hypothesis that Densest k-Subgraph is hard to approximate within k^{1-δ} for any δ > 0, yielding (2 - ε) inapproximability for DALkS. These transfers hold in both the standard and the parameterized-by-k regimes. The exact version of DALkS is W[1]-hard parameterized by k.

What carries the argument

A polynomial-time reduction from Densest k-Subgraph instances to Densest At-Least-k-Subgraph instances that maps the approximation gap such that a ρ-approximation for DALkS yields a (3/2)ρ-approximation for DkS.

Load-bearing premise

Densest k-Subgraph itself has no constant-factor approximation algorithm.

What would settle it

A polynomial-time algorithm that approximates Densest k-Subgraph to within any constant factor.

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

If this is right

  • DALkS has no (3/2 - ε)-approximation unless DkS does.
  • Under the k^{1-δ} hardness hypothesis for DkS, DALkS has no (2 - ε)-approximation.
  • The exact DALkS problem admits no FPT algorithm parameterized by k unless FPT = W[1].
  • The same conditional hardness statements hold when both problems are parameterized by k.

Where Pith is reading between the lines

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

  • The reduction technique separates the parameterized hardness of DALkS from the Small Set Expansion Hypothesis used in prior work.
  • If the gap between the 3/2 and 2 factors can be closed by a refined construction, constant-factor hardness of DkS would imply full 2-hardness of DALkS.
  • The results suggest examining whether other relaxations of exact-k subgraph problems inherit similar hardness thresholds via analogous reductions.

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 / 2 minor

Summary. The manuscript presents a simple reduction from Densest k-Subgraph (DkS) to Densest At-Least-k-Subgraph (DALkS). Under the hypothesis that DkS has no constant-factor approximation, it shows that DALkS has no (3/2 - ε)-approximation for any ε > 0; under the stronger hypothesis that DkS has no k^{1-δ}-approximation, DALkS has no (2 - ε)-approximation. Both results hold in the standard and k-parameterized settings. The paper also proves that exact DALkS is W[1]-hard parameterized by k. It recalls the known 2-approximation algorithm for DALkS.

Significance. The results strengthen the understanding of DALkS approximability by deriving conditional hardness directly from DkS hypotheses rather than the Small Set Expansion Hypothesis, and the parameterized hardness statements are new. The explicit conditional framing and the W[1]-hardness result are correctly stated.

minor comments (2)
  1. [Abstract] The abstract refers to the reduction but does not cite the section or theorem number where the construction and factor analysis appear; adding an explicit pointer would improve readability.
  2. In the statement of the stronger hypothesis (roughly k^{1-δ} hardness for DkS), the precise formal statement of the hypothesis should be given as a numbered assumption or definition for clarity when citing it in the parameterized setting.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, accurate summary of our results, and recommendation to accept. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; results conditional on external DkS hardness

full rationale

The paper's central results consist of polynomial-time reductions from Densest k-Subgraph (DkS) to Densest At-Least-k-Subgraph (DALkS) that transfer inapproximability factors, plus a standard W[1]-hardness reduction for the exact version. All hardness statements are explicitly conditional on external hypotheses about DkS (constant-factor or k^{1-δ}-factor inapproximability) that are not derived or fitted within the paper itself. No self-definitional equations, fitted inputs renamed as predictions, load-bearing self-citations, or ansatzes smuggled via prior work appear; the derivation chain is self-contained once the external DkS assumption is granted.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

All hardness statements are conditional on unproven hypotheses about the approximability of Densest k-Subgraph; no new axioms, free parameters, or invented entities are introduced.

axioms (1)
  • domain assumption Densest k-Subgraph has no constant-factor approximation (or no k^{1-δ} approximation under the stronger hypothesis)
    The inapproximability claims for DALkS are derived directly from this hypothesis via the stated reduction.

pith-pipeline@v0.9.1-grok · 5888 in / 1461 out tokens · 45229 ms · 2026-06-29T20:01:58.275007+00:00 · methodology

0 comments
read the original abstract

We study the Densest At-Least-$k$-Subgraph (DAL$k$S) problem, in which we are given an undirected graph $G$ and an integer $k$, and the goal is to find a subgraph of $G$ with at least $k$ vertices with maximum density. The best-known algorithm, independently discovered by Khuller and Saha (2009) and by Andersen (2007), yields a 2-approximation for DAL$k$S in polynomial time. In this note, we provide a (simple) reduction from Densest $k$-Subgraph (D$k$S) to Densest At-Least-$k$-Subgraph, which shows that, if D$k$S is hard to approximate to within any constant factor, then DAL$k$S is hard to approximate to within $(3/2 - \varepsilon)$ factor for every $\varepsilon > 0$. This holds in both the normal (non-parameterized) and the parameterized (by $k$) settings. We then generalize the reduction to provide a tight $(2 - \varepsilon)$ factor hardness of approximating Densest At-Least-$k$-Subgraph, albeit under a stronger hypothesis which roughly states that Densest $k$-Subgraph is hard to approximate to within $k^{1 - \delta}$ factor for any constant $\delta > 0$. Once again, this extends naturally to the parameterized setting. Previously, $(2 - \varepsilon)$ factor inapproximability for DAL$k$S was only known under the Small Set Expansion Hypothesis (Bergner, 2013; Manurangsi, 2017), which does not apply to the parameterized version of the problem. Furthermore, we show that the exact version of DAL$k$S is W[1]-hard (parameterized by $k$).

Figures

Figures reproduced from arXiv: 2605.25464 by Bundit Laekhanukit, Ohad Trabelsi, Pasin Manurangsi.

Figure 1
Figure 1. Figure 1: An Illustration of the reduction in Lemma [PITH_FULL_IMAGE:figures/full_fig_p008_1.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

31 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Inapproximability of densest k -subgraph from average case hardness

    Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein. Inapproximability of densest k -subgraph from average case hardness. Unpublished Manuscript, 2011

    2011

  2. [2]

    Finding dense subgraphs with size bounds

    Reid Andersen and Kumar Chellapilla. Finding dense subgraphs with size bounds. In WAW , pages 25--37, 2009

    2009

  3. [3]

    Finding large and small dense subgraphs

    Reid Andersen. Finding large and small dense subgraphs. CoRR , abs/cs/0702032, 2007

    work page internal anchor Pith review Pith/arXiv arXiv 2007

  4. [4]

    Polynomial integrality gaps for strong SDP relaxations of densest k -subgraph

    Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, and Yuan Zhou. Polynomial integrality gaps for strong SDP relaxations of densest k -subgraph. In SODA , pages 388--405, 2012

    2012

  5. [5]

    Small set expansion

    Lilli Bergner. Small set expansion. Master's thesis, École Polytechnique Fédérale de Lausanne, Switzerland, January 2013

    2013

  6. [6]

    ETH hardness for densest- k -subgraph with perfect completeness

    Mark Braverman, Young Kun - Ko, Aviad Rubinstein, and Omri Weinstein. ETH hardness for densest- k -subgraph with perfect completeness. In SODA , pages 1326--1341, 2017

    2017

  7. [7]

    From Gap-ETH to FPT -inapproximability: Clique, dominating set, and more

    Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, and Luca Trevisan. From Gap-ETH to FPT -inapproximability: Clique, dominating set, and more. In FOCS , pages 743--754, 2017

    2017

  8. [8]

    A new conjecture on hardness of 2- CSP 's with implications to hardness of densest k-subgraph and other problems

    Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, and Zihan Tan. A new conjecture on hardness of 2- CSP 's with implications to hardness of densest k-subgraph and other problems. In ITCS , pages 38:1--38:23, 2023

    2023

  9. [9]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: on completeness for W[1] . Theor. Comput. Sci. , 141(1 & 2):109--131, 1995

    1995

  10. [10]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity . Texts in Computer Science. Springer, 2013

    2013

  11. [11]

    Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover

    Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC) , 23:128, 2016

    2016

  12. [12]

    Relations between average case complexity and approximation complexity

    Uriel Feige. Relations between average case complexity and approximation complexity. In STOC , pages 534--543, 2002

    2002

  13. [13]

    Andreas Emil Feldmann, Karthik C. S. , Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms , 13(6):146, 2020

    2020

  14. [14]

    The dense k -subgraph problem

    Uriel Feige, Guy Kortsarz, and David Peleg. The dense k -subgraph problem. Algorithmica , 29(3):410--421, 2001

    2001

  15. [15]

    On set expansion problems and the small set expansion conjecture

    Rajiv Gandhi and Guy Kortsarz. On set expansion problems and the small set expansion conjecture. Discrete Applied Mathematics , 194:93--101, 2015

    2015

  16. [16]

    An FPT algorithm beating 2-approximation for k -cut

    Anupam Gupta, Euiwoong Lee, and Jason Li. An FPT algorithm beating 2-approximation for k -cut. In SODA , pages 2821--2837, 2018

    2018

  17. [17]

    On the complexity of k - SAT

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k - SAT . J. Comput. Syst. Sci. , 62(2):367--375, March 2001

    2001

  18. [18]

    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, December 2001

    2001

  19. [19]

    Large cliques elude the metropolis process

    Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms , 3(4):347--359, 1992

    1992

  20. [20]

    Ruling out PTAS for graph min-bisection, dense k -subgraph, and bipartite clique

    Subhash Khot. Ruling out PTAS for graph min-bisection, dense k -subgraph, and bipartite clique. SIAM J. Comput. , 36(4):1025--1071, 2006

    2006

  21. [21]

    On finding dense subgraphs

    Samir Khuller and Barna Saha. On finding dense subgraphs. In ICALP , pages 597--608, 2009

    2009

  22. [22]

    Expected complexity of graph partitioning problems

    Lud e k Ku c era. Expected complexity of graph partitioning problems. Discrete Appl. Math. , 57(2-3):193--212, February 1995

    1995

  23. [23]

    A parameterized approximation scheme for min k -cut

    Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. A parameterized approximation scheme for min k -cut. SIAM J. Comput. , 53(6):S20--205, 2024

    2024

  24. [24]

    Almost-polynomial ratio ETH -hardness of approximating densest k -subgraph

    Pasin Manurangsi. Almost-polynomial ratio ETH -hardness of approximating densest k -subgraph. In STOC , pages 954--961, 2017

    2017

  25. [25]

    Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis

    Pasin Manurangsi. Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis. Algorithms , 11(1):10, 2018

    2018

  26. [26]

    A note on max k -vertex cover: Faster FPT-AS , smaller approximate kernel and improved approximation

    Pasin Manurangsi. A note on max k -vertex cover: Faster FPT-AS , smaller approximate kernel and improved approximation. In SOSA , pages 15:1--15:21, 2019

    2019

  27. [27]

    Parameterized complexity and approximation algorithms

    D \' a niel Marx. Parameterized complexity and approximation algorithms. Comput. J. , 51(1):60--78, 2008

    2008

  28. [28]

    A birthday repetition theorem and complexity of approximating dense CSP s

    Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense CSP s. In ICALP , pages 78:1--78:15, 2017

    2017

  29. [29]

    The strongish planted clique hypothesis and its consequences

    Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The strongish planted clique hypothesis and its consequences. In ITCS , pages 10:1--10:21, 2021

    2021

  30. [30]

    Graph expansion and the unique games conjecture

    Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In STOC , pages 755--764, 2010

    2010

  31. [31]

    Dense subgraphs with restrictions and applications to gene annotation graphs

    Barna Saha, Allison Hoch, Samir Khuller, Louiqa Raschid, and Xiao - Ning Zhang. Dense subgraphs with restrictions and applications to gene annotation graphs. In RECOMB , pages 456--472, 2010

    2010