{"id":"460b9f67-e5ad-4d0a-b1ed-0af4d0cf3f8e","arxiv_id":"2502.01381","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors prove that two fairness-constrained variants of the densest subgraph problem over graph snapshots are NP-hard and give integer-programming and greedy algorithms.","lead":"This paper studies how to find a dense community in a network that changes over time while keeping the density roughly equal in every time snapshot. It proves that the fair versions are computationally hard and offers exact and fast approximate algorithms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified to the central NP-hardness and inapproximability claims.","rationale":"The paper's strongest claim is that FDS and SDS are NP-hard and SDS has no multiplicative polynomial-time approximation. I examined the reductions in Section 3. Proposition 1 constructs two snapshots over a common vertex set and proves that d(S,G)=(k−1)/2 iff a k-clique exists. A slight gap is that the proof starts from equality, whereas NP-hardness of the decision problem requires the threshold version; however, the inequalities in the proof actually establish the stronger statement that any feasible S (with equal densities) has total density at most (k−1)/2, with equality only for a clique. This makes the reduction valid. Proposition 2's inapproximability uses the standard argument that a multiplicative approximation would have to output value 0 when the optimum is 0, thereby solving k-Clique; this is correct. The reader's weakest assumption about common vertex sets is a stated modeling premise, not an internal inconsistency: the definitions in Section 2 explicitly require Gi=(V,Ei) over the same node set, and the reductions and IPs are consistent with that premise. The remaining issues are presentation-level: the rational-gap proof in Proposition 4 contains a typo (the gap is 1/n^2, not n−2), and the SDS-IP stopping condition in Section 4.2 is likely misstated (should be U−L≤εL rather than U−L≤(1+ε)L). These are fixable and do not affect the central complexity results. Therefore, no load-bearing objection is identified, and the reader's CONDITIONAL verdict should stand unchanged.","tokens_in":15037,"tokens_out":24322,"duration_ms":202103,"concrete_test":"Independently re-derive the upper bound in Proposition 1: show that for any S with d(S,G1)=d(S,G2), d(S,G) ≤ (k−1)/2, with equality iff W is a k-clique. This confirms the reduction is threshold-correct and closes the equality/inequality gap in the published proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claims are sound. The FDS and SDS reductions from k-Clique are correct: for α=0, any feasible S must have equal densities across the two snapshots, and the inequalities in Proposition 1 imply that unless |W|=|T|=k and W is a clique, both densities are strictly below (k−1)/4, so total density cannot reach the threshold. The SDS inapproximability follows from the standard zero-OPT argument. The stated common-vertex-set premise is a modeling boundary, not an internal inconsistency. Remaining issues are presentation typos (e.g., the rational-gap bound written as 'n−2' instead of 'n^{-2}', and the SDS-IP stopping condition) and omitted proofs for Propositions 6 and 7, which the reader already flagged; none of these undermines the central NP-hardness or inapproximability results.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines two multi-snapshot densest-subgraph problems with fairness constraints: FDS (maximize total density subject to the range of per-snapshot densities being at most alpha) and SDS (minimize the density range subject to total density at least sigma). It proves FDS NP-hard and SDS NP-hard and inapproximable unless P=NP, using reductions from k-Clique. It then proposes exact algorithms based on fractional programming and integer linear programming (FDS-IP and SDS-IP) with (1+epsilon)-type guarantees, two polynomial-time greedy heuristics (FDS-Grd and SDS-Grd), and an IP-based solver for the existing MDS baseline. Experiments on synthetic and real-world datasets evaluate recovery of a planted fair component, solution quality, and runtime; a DBLP case study illustrates trade-offs between density and fairness.","tokens_in":15133,"tokens_out":15686,"duration_ms":136889,"significance":"The complexity results are the paper's main contribution and they appear sound: the alpha=0 reduction forces equal densities, and the threshold argument correctly forces a balanced set W union U of size 2k and a clique. The SDS inapproximability via the zero-OPT argument is also standard and correct. The IP formulations are a reasonable way to solve the problems exactly on moderate instances, and the synthetic experiments include a planted ground-truth component with Jaccard recovery, which is a useful form of validation. The paper is honest about the exponential worst case of the exact solvers and the lack of guarantees for the heuristics. My main concerns are formal: Proposition 4 contains an incorrect sentence in the exactness proof, the proofs of Propositions 6 and 7 are omitted, and one reported experimental solution appears infeasible; none of these undermines the core reductions, but they need to be fixed before the paper is fully acceptable.","major_comments":[{"comment":"In the exactness proof, the statement 'd(S, G) is a rational number with a numerator of at most n' is false; the correct invariant is that d(S, G) can be written with denominator |S| <= n, so two distinct achievable densities differ by at least 1/n^2. The displayed bounds 'gamma* − gamma > n−2' and 'U − L ≤ n−2' appear to be rendering errors for n^{-2}. As written the proof of the exactness claim gamma = gamma* does not go through; please restate the rational-gap argument with the correct denominator bound and exponents.","section":"§4.1, Proposition 4"},{"comment":"The proofs of Propositions 6 and 7 are omitted with the note that they are similar to Proposition 4. These propositions provide the approximation and exactness guarantees for SDS-IP and MDS-IP, so they are load-bearing for the algorithmic claims. Please supply complete proofs or detailed proof sketches; the SDS case in particular involves a minimization search with an upper-bound return, so the exactness argument is not literally identical to the FDS case.","section":"§4.2 and §4.5, Propositions 6 and 7"},{"comment":"The binary search for SDS-IP is described as stopping when 'U − L ≤ (1 + epsilon)L', but this condition is inconsistent with the claimed gamma <= (1+epsilon)gamma* guarantee; it should be U − L <= epsilon L (as in FDS-IP), and the search interval should start at L = 0 and U = (n−1)/2 (or another stated bound). Please correct the stopping rule and specify the initialization.","section":"§4.2, SDS-IP"},{"comment":"In the Twitter-user dataset with alpha = 0.3, the FDS-IP row reports Δ = 0.5, which violates the feasibility constraint Δ <= alpha. Since Constraint (5) should prevent this, either the table entry or the implementation is wrong. Please correct the entry and verify that every reported solution satisfies its stated alpha; the same check should be applied to Table 4.","section":"Table 3"}],"minor_comments":[{"comment":"When Δ(S,G)=0, the common density is at least (k−1)/4 (because the total density must be at least sigma=(k−1)/2), not necessarily equal to it; the subsequent clique argument still works with '>=' in place of '=' and should be updated.","section":"§3, Proposition 2"},{"comment":"The caption describes alpha as the 'minimum value of the allowed induced density difference', but per Problem 2 it is the maximum allowed difference.","section":"Table 3 caption"},{"comment":"The text refers to 'Figure 1d', but the figure only contains panels (a)–(c); the reference should be to Figure 1c.","section":"§6.5"},{"comment":"The update rule for the greedy heuristic is only loosely specified; please state how ties are broken, what 'while changes to Δ(S)' means formally, and give a termination and running-time bound for the algorithm.","section":"§4.3, Algorithm 1"},{"comment":"The formatting of several rows (e.g., Twitter-#) is garbled, with missing or ambiguous cells; please provide a clean table with clearly separated IP and GR columns.","section":"Table 4"},{"comment":"The description of FDS-Grd's first phase says it runs SDS-Grd for sigma in {i/k * dtds}, but it does not state a default for k in the main text; the experimental section mentions k=20 then k=100, so please state the parameter setting in the algorithm description.","section":"§4.4"}],"recommendation":"major_revision","confidential_remarks":"This is a competently executed graph-mining paper with solid hardness reductions. I recommend major revision rather than rejection: the core theory is defensible, but the manuscript needs corrected proofs and a repaired experimental table. The novelty relative to prior work is moderate but adequate for a specialized graph-mining or data-engineering venue; the paper is not a pure theory paper because of the heuristics and experimental focus, but it fits the journal's scope if the formal gaps are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper defines two natural fairness-constrained variants of densest subgraph on graph snapshots: FDS, maximizing total density subject to a max allowed range alpha between per-snapshot densities, and SDS, minimizing that range subject to a minimum total density sigma. Both problems are new in this exact form; prior fair-densest work colors nodes in a single graph, while this constrains density across snapshots. The NP-hardness and inapproximability claims are the main theoretical contribution, and they check out. The reduction from k-Clique for alpha=0 is clean: it forces equal densities across the two snapshots, and the counting argument correctly pins down a k-clique. The SDS inapproximability follows from the same zero-gap construction. I agree with the stress-test note: on reading the proof, the central claims hold.\n\nThe paper also does something practical. The IP formulations correctly encode the problems, and the binary-search/fractional-programming wrapper is standard but competently executed. The greedy heuristics are sensible, and the experiments, while not extensive in scope, do show the exact IPs recover a planted ground truth and produce reasonable trade-offs on real data. The DBLP case study illustrates the intended use well.\n\nSoft spots are minor but real. Propositions 6 and 7 are stated without proof, with 'similar to... therefore omitted'; that is acceptable for a supplement but weak in a main text claiming approximation guarantees. Proposition 4's exactness argument has a typo-riddled gap: the text says a density rational has 'numerator of at most n' and then writes 'γ∗−γ > n−2' where it should be 'n^{-2}'. The SDS-IP stopping condition has a suspicious inequality. The supplementary PDF is unfinished, with placeholder citations and no author block; that should not go out as-is. The single-run experiments without variance reporting are a limitation, but the synthetic ground-truth recovery is still meaningful. The common-vertex-set assumption is stated up front; it is a modeling boundary, not an error.\n\nBottom line: this is a solid subfield contribution with correct hardness results and usable algorithms. Send it to review. A good referee will ask for the missing proofs, the typo fixes, and a cleaned supplement, but the core work deserves referee time.\n\nBest,\n[Name]","headline":"A useful, correct addition to the densest-subgraph toolkit; the central hardness results hold, and the soft spots are presentation-level rather than load-bearing.","tokens_in":15685,"tokens_out":2118,"would_cite":true,"duration_ms":19249,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68R10","90C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that two fair variants of the densest subgraph problem across graph snapshots are NP-hard, gives exact integer-programming algorithms and greedy heuristics, and evaluates them on real and synthetic data.","keywords":["fair densest subgraph","graph snapshots","temporal networks","NP-hardness","integer programming","fractional programming","greedy heuristic","density range"],"falsifier":"Run the $\\alpha = 0$ reduction on a graph $H$ known to have no $k$-clique: if any subset $S$ yields $d(S,G_1) = d(S,G_2) = (k-1)/4$, the reduction is wrong. More broadly, an exact polynomial-time algorithm for FDS on two snapshots with equal vertex sets would refute NP-hardness unless P=NP.","tokens_in":14812,"feed_emoji":"⚖️","tokens_out":5949,"duration_ms":49651,"temperature":0.7,"pith_summary":"This paper studies how to find a dense subgraph common to several graph snapshots without letting one snapshot dominate the density score. It introduces and analyzes two optimization problems: FDS, which maximizes the sum of per-snapshot densities subject to the gap between the maximum and minimum snapshot density being at most $\\alpha$, and SDS, which minimizes that gap subject to a lower bound $\\sigma$ on the total density. The paper's central claims are that both problems are NP-hard, that SDS has no multiplicative polynomial-time approximation unless P=NP, and that the hardness can be met in practice with exact integer-programming solvers plus polynomial-time heuristics. The motivation is fairness: standard sum-density maximization can return a subgraph that is dense in one time window and empty in all others, whereas these formulations keep the induced density spread across snapshots.","feed_headline":"Fair densest subgraphs across snapshots are NP-hard","feed_subtitle":"A density cap or density gap objective flips an easy graph-mining problem; exact IP and greedy solvers are provided.","key_machinery":"The load-bearing mechanism is the density functional $d(S, G_i) = |E(S, G_i)|/|S|$ together with the range functional $\\Delta(S,\\mathcal{G}) = \\max_i d(S,G_i) - \\min_i d(S,G_i)$. The integer programs convert vertex selection into binary variables $y_i$ and edge selection into $x_{ij}$, forcing $x_{ij} = \\min(y_i, y_j)$, and encode the fairness constraint $b(S,\\mathcal{G}) \\le \\alpha|S|$, where $b(S,\\mathcal{G}) = \\max_i m(S,G_i) - \\min_i m(S,G_i)$. Because the density objective is a fraction, the paper uses Dinkelbach-style fractional programming: instead of maximizing $d(S,\\mathcal{G})$ directly, it maximizes $\\sum_i m(S,G_i) - \\gamma|S|$ for a guessed $\\gamma$ and binary-searches $\\gamma$, which is the device that turns each density query into one integer linear program.","core_discovery":"On the paper's own terms, the discovery is that imposing near-equal densities across snapshots flips the classic densest subgraph problem from polynomial-time solvable to NP-hard. The hardness holds in the extreme case $\\alpha = 0$, where both snapshots must induce exactly the same density, and the proof reduces from $k$-Clique by building two snapshots over a common vertex set: $G_1$ is the clique-test graph plus $k$ isolated helper vertices, and $G_2$ is a $k$-clique on those helpers. A subset achieves equal densities and total density $(k-1)/2$ exactly when the helper vertices are balanced with a $k$-clique in $G_1$. The same construction shows SDS is inapproximable. For solving the problems, the paper defines auxiliary objectives $\\text{FDS}(\\gamma)$ and $\\text{SDS}(\\gamma)$ that subtract $\\gamma$ times the vertex count from edge counts, solves them as integer linear programs, and wraps them in a binary search that gives a $(1+\\varepsilon)$ approximation, or an exact result once $\\varepsilon$ is below the gap between distinct density values.","pith_inferences":["A likely next test is whether the hardness survives a different density measure, such as $m(S)/\\binom{|S|}{2}$ or triangle density, which the authors explicitly leave to future work; those measures change the fractional-programming structure and may shift the boundary.","The equivalence $\\Delta(S,\\mathcal{G}) \\le \\alpha \\iff b(S,\\mathcal{G}) \\le \\alpha|S|$ depends on dividing edge counts by the same $|S|$; if snapshots had different vertex sets or weights, the IP constraint would need a different normalization, so the complexity results should be read within the common-vertex-set model.","For very large snapshot sequences the exact IP solvers will be limited by exponential worst-case runtime; a promising practical direction, not explored here, is to strengthen the LP relaxation or add cutting planes so the binary search runs faster than the reported one-hour cutoffs.","The case study hints at a concrete use: tuning $\\alpha$ or $\\sigma$ lets an analyst trade total density against venue or temporal diversity, something the minimum-densest-subgraph baseline cannot do since it has no trade-off parameter."],"forward_implications":["The unconstrained total-density problem on graph sequences is polynomial-time solvable, but adding any fixed density-spread constraint makes it NP-hard, even for $\\alpha = 0$.","The smallest-difference variant SDS has no polynomial-time multiplicative approximation unless P=NP, so the exact IP solver is the only way to get provable answers.","The binary-search IP algorithms return a solution within a $(1+\\varepsilon)$ factor, and become exact when $\\varepsilon$ is small enough that the search interval cannot straddle two distinct density values.","The greedy heuristics recover planted fair components in synthetic data and produce reasonable solutions on real datasets, offering a practical alternative when the IP solvers are too slow.","The DBLP case study indicates that tuning $\\alpha$ or $\\sigma$ gives an analyst a direct trade-off between total density and diversity across venues or time snapshots."],"supporting_citations":[{"why":"Supplies the polynomial-time exact algorithm for the single-graph densest subgraph that the paper extends and uses as a baseline for the flattened TDS problem.","marker":"[10]"},{"why":"Provides the greedy approximation algorithm and linear-programming view of the classic densest subgraph problem.","marker":"[4]"},{"why":"Defines the total densest subgraph (TDS) formulation on graph sequences, which is the unconstrained starting point for both FDS and SDS.","marker":"[20]"},{"why":"Introduces the minimum densest subgraph (MDS) problem used as a comparison baseline and as the target of an additional exact algorithm.","marker":"[12]"},{"why":"Supplies the fractional programming technique underlying the binary-search exact algorithms for FDS, SDS, and MDS.","marker":"[6]"},{"why":"Shows that the related dense common subgraph variant is NP-hard, providing context for the hardness results.","marker":"[5]"}],"fun_headline_variants":["Fairness cap makes densest subgraph NP-hard","Equal-density requirement kills polynomial time","NP-hard for fair dense subgraphs across snapshots","Balanced density search across graphs is NP-hard","Density fairness: NP-hard with multiple graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All results assume the snapshots share one vertex set and density is $|E(S)|/|S|$; if either changes, the $k$-Clique reductions and the constraint encoding $b(S,\\mathcal{G}) \\le \\alpha|S|$ would have to be rebuilt.","fun_headline_variants_meta":{"raw":{"variants":["Fairness cap makes densest subgraph NP-hard","Equal-density requirement kills polynomial time","NP-hard for fair dense subgraphs across snapshots","Balanced density search across graphs is NP-hard","Density fairness: NP-hard with multiple graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000764,"raw_usage":{"total_tokens":3422,"prompt_tokens":1008,"completion_tokens":2414,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":624,"completion_tokens_details":{"reasoning_tokens":2344}},"tokens_in":624,"tokens_out":2414,"duration_ms":18152,"temperature":1.0,"reasoning_tokens":2344,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T15:30:54.322500+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the $\\alpha = 0$ reduction on a graph $H$ known to have no $k$-clique: if any subset $S$ yields $d(S,G_1) = d(S,G_2) = (k-1)/4$, the reduction is wrong. More broadly, an exact polynomial-time algorithm for FDS on two snapshots with equal vertex sets would refute NP-hardness unless P=NP.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-time exact algorithm for the single-graph densest subgraph that the paper extends and uses as a baseline for the flattened TDS problem."},{"cited_title":"In: APPROX","cited_arxiv_id":null,"evidence_quote":"Provides the greedy approximation algorithm and linear-programming view of the classic densest subgraph problem."},{"cited_title":"DMKD 33(5), 1417–1445 (2019)","cited_arxiv_id":null,"evidence_quote":"Defines the total densest subgraph (TDS) formulation on graph sequences, which is the unconstrained starting point for both FDS and SDS."},{"cited_title":"In: ECMLPKDD","cited_arxiv_id":null,"evidence_quote":"Introduces the minimum densest subgraph (MDS) problem used as a comparison baseline and as the target of an additional exact algorithm."},{"cited_title":"M anagement science 13(7), 492–498 (1967) Fair densest subgraph across multiple graphs 17","cited_arxiv_id":null,"evidence_quote":"Supplies the fractional programming technique underlying the binary-search exact algorithms for FDS, SDS, and MDS."}],"review_version":1}