{"id":"3a2cc717-58b0-4c24-b138-5baa02b4ef92","arxiv_id":"2608.07674","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For the new NP-hard perfect fair-triangle packing problem, the paper provides a deterministic 1/3-approximation and a randomized (16/47 - epsilon)-approximation in polynomial time.","lead":"This paper introduces a new weighted triangle packing problem in which every group of three vertices must contain both red and blue vertices, and proves the problem is NP-hard. It gives a simple deterministic 1/3-approximation and a more complex randomized (16/47 - epsilon)-approximation, the first approximation guarantees for this problem.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 7's proof of the degree-1/2 probability is incomplete; the lemma is likely true, but the randomized ratio rests on it.","rationale":"After reading the full manuscript, the NP-hardness reduction, the deterministic 1/3-approximation, and the algebraic structure of the randomized analysis appear coherent. The final expectation identity is written loosely as E[T] = max{...} instead of E[max{...}], but the subsequent convex-combination inequality is valid. The O(n^{2.5}) runtime claimed for maximum-weight matching in Lemma 11 mis-cites the unweighted Micali-Vazirani algorithm; replacing it by an O(n^3) weighted-matching subroutine keeps the claimed O(n^4) total running time, so this is not a load-bearing error. The one place where an unproved or false statement could alter the central bound is Lemma 7's degree probability. The reader identified Lemma 7 as the weak spot; I agree on the lemma, though the precise defect is that the proof fails to rule out both incident edges being deleted, rather than merely that the two deletion events are dependent. The claimed value 1/2 is in fact correct, and a short matching argument repairs the proof, so this is a proof gap rather than a refutation. The paper should add that missing case analysis or the one-line deleted-edges-form-a-matching argument before the central claims are treated as fully rigorous. Therefore the CONDITIONAL verdict is appropriate and should remain unchanged.","tokens_in":24873,"tokens_out":35784,"duration_ms":333857,"concrete_test":"Enumerate all random choices of Figure 7 for every even cycle length c with 4 <= c <= 2/epsilon (or at least c = 4, 6, 8, 10, 12): for each random rotation e1 and each coin outcome, compute the degree of every vertex in C1 and the survival of every edge; verify Pr[d_{C1}(u)=1] = 1/2 for all u and Pr[e in E(C1)] = 3/4 for all e. Equivalently, prove in one paragraph that the set of deleted edges is a matching and each edge has marginal deletion probability 1/4; then d(u)=1 iff exactly one incident edge is deleted, whose probability is 1/4 + 1/4 = 1/2. Either check would settle whether Lemma 7 and the dependent lemmas stand.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is the proof of Lemma 7 in Section 5.4. The randomized (16/47 - epsilon)-approximation uses the assertion Pr[d_{C1}(u)=1] = 1/2 in Lemmas 9, 10, 13, and 14; if that probability is wrong, the expected-weight bounds for T2, T3, and T4, and hence Theorem 3, fail. The proof argues that for the two incident edges e1 and e2, d_{C1}(u)=1 if e1 not in E(C1) or e2 not in E(C1), and then adds the two marginal deletion probabilities 1/4. This step is not justified as written: the displayed condition would also hold if both e1 and e2 were deleted, in which case d_{C1}(u)=0. The preceding observation |{e1,e2} ∩ E(C1)| <= 1 only says at most one of the two edges remains; it does not rule out the both-deleted case. In the actual algorithm of Figure 7 the deleted edges form a matching (no two deleted edges are adjacent), so both incident edges are never deleted and the lemma is true, but the manuscript nowhere supplies this verification or a complete case analysis. Thus the central probability is asserted rather than proved, and every downstream lemma that multiplies by 1/2 inherits the gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the perfect fair-triangle packing problem (PFTP), in which the vertices of an edge-weighted complete graph on 3n vertices are colored red or blue and one seeks a partition into n triangles, each containing vertices of both colors, maximizing total edge weight. The authors prove that PFTP is NP-hard even when the number of red vertices equals n, and they design two approximation algorithms: a deterministic 1/3-approximation running in O(n^3) time and a randomized (16/47 - epsilon)-approximation running in O(n^4) time. The deterministic algorithm combines maximum-weight red and blue matchings with a maximum-weight bichromatic matching. The randomized algorithm computes a maximum-weight [1,2]-factor in the bichromatic graph, decomposes long components, classifies bichromatic edges into five types, and constructs five candidate packings T0 through T4, using random cycle-breaking and matching-based path assembly. The central technical claim is the expected approximation ratio of 16/47 - epsilon, which is obtained by taking a convex combination of lower bounds on the five candidate packings.","tokens_in":25111,"tokens_out":12814,"duration_ms":109199,"significance":"If correct, this is a sensible and meaningful first treatment of a natural fairness-constrained packing problem. The reduction from 3-dimensional matching is standard but establishes the claimed NP-hardness at the boundary r = n. The deterministic 1/3-approximation has a clean and easily checkable proof. The randomized algorithm is technically inventive: the use of a maximum-weight [1,2]-factor, the type-based partition of bichromatic edges, and the random cycle-breaking procedure to produce odd alternating paths are nontrivial and go beyond a direct reduction to weighted 3-set packing. The paper gives explicit pseudocode for every subroutine and states concrete constants. The main caveats are an incomplete proof of the key probability in Lemma 7 and an incorrect runtime citation for weighted matchings; both appear to be local and repairable without changing the claimed results.","major_comments":[{"comment":"The proof of Pr[d_{C1}(u)=1]=1/2 is incomplete. The text observes that |{e1,e2} ∩ E(C1)| ≤ 1 and then says d_{C1}(u)=1 if e1∉E(C1) or e2∉E(C1), but this condition is also satisfied when both incident edges are deleted, in which case d_{C1}(u)=0. The missing fact is that the edges deleted in Figure 7 form a matching: in Step 3 they are spaced four positions apart along the cycle, and in Step 4 the additional edge e_{c-1} is not adjacent to any of e1,e5,...,e_{c-5}. With this observation, exactly one of the two incident edges is deleted with probability 1/4+1/4=1/2 and the lemma is true. As written, however, the probability 1/2 used repeatedly in Lemmas 9, 10, 13, and 14, and hence in the expectation bound of Theorem 3, is asserted rather than proved. The authors should add the missing case analysis or explicitly prove that the deleted edges form a matching.","section":"Section 5.4, Lemma 7"},{"comment":"The runtime analysis claims O(n^{2.5}) time for computing maximum-weight matchings by citing reference [18], but [18] (Micali and Vazirani) is an algorithm for unweighted maximum-cardinality matching with running time O(sqrt(|V|)|E|); it does not compute maximum-weight matchings. The matchings M2, M3, M4, and M_P are weighted. Replacing this citation with Gabow's weighted matching algorithm [13] or the [f,g]-factor reduction of [14] gives O(n^3) per matching. Since only a constant number of such matchings are computed and the dynamic program in Section 5.2 dominates, Theorem 3's O(n^4) bound still follows, but the stated O(n^{2.5}) bounds in Lemmas 11, 13, and 14 are not supported as written.","section":"Section 5.5, Lemmas 11, 13, 14"}],"minor_comments":[{"comment":"The displayed identity E[T] = max{w(T0), w(T1), E[T2], E[T3], E[T4]} should be an inequality: E[max Xi] >= max E[Xi]. The subsequent proof only needs the inequality, so this is a presentation issue rather than a correctness problem.","section":"Section 5.8, Theorem 3"},{"comment":"In the conditional probability computation, the equality Pr[A1(u,t)|e∈M'_2] = 2Pr[A1(u,t)] uses the independence of random choices on different cycles of C. Please state explicitly that cycles are broken independently and that v lies in a different cycle than u and t, so that A1(u,t) is independent of A4.","section":"Section 5.5, Lemma 10"},{"comment":"There are numerous typos and grammatical slips, e.g., 'constrcut' in Lemma 5, 'exsits' in Section 5.2, 'edpoint' in Section 5.7, 'prepocessing' in Table 1, 'mathings' in Lemma 2, and the author name 'Hassan' in reference [16] should be 'Hassin'. A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within scope and the two issues above are local and fixable. The missing matching argument in Lemma 7 is the key thing to add; the runtime citation error does not threaten the final O(n^4) claim once corrected. I see no circularity or novelty problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: PFTP is a genuinely new problem, and the paper is mostly solid. The NP-hardness reduction from 3-DM is convincing, the deterministic 1/3-approximation is clean, and the randomized (16/47 - epsilon) analysis is an elaborate but coherent piece of work. The five-type decomposition of bichromatic edges and the way the [1,2]-factor is broken into odd alternating paths are substantive contributions. The algebra in Theorem 3 checks, and the overall structure is sound.\n\nThe soft spots are real but not fatal. The proof of Lemma 7, the claim that every vertex has degree exactly 1 in C1 with probability 1/2, is incomplete as written. The paper derives this from the two incident edges each being deleted with probability 1/4 and says the union bound gives 1/2. That only works if the two deletion events are mutually exclusive, and the manuscript never verifies that the deleted edges form a matching. The stress-test note is right: the lemma is likely true because the algorithm's deletion pattern never removes two incident edges, but the proof needs an explicit case analysis or a sentence establishing mutual exclusivity. Since Lemmas 9, 11, 13, and 14 all rely on this probability, this needs to be fixed before Theorem 3 is fully rigorous.\n\nThere is also a minor citation error: Lemmas 11, 13, and 14 claim O(n^2.5) time for computing maximum-weight matchings, citing Micali-Vazirani [18], which solves unweighted matching. Weighted matching in general graphs needs a different algorithm (e.g., Gabow's O(n^3) or similar). The O(n^4) bound in Theorem 3 survives because the matching step is not the bottleneck, so this is a fixable oversight, not a structural problem.\n\nThe citation to the authors' own [20] for Lemma 8 is fine, since a proof sketch is included and the lemma itself is not the load-bearing step. The reduction from PFTP to W3SP when r=n and the counterexample for general r are useful and clearly explained.\n\nWho is this for? Anyone working on triangle packing, fair clustering, or approximation algorithms for constrained packing problems. The paper deserves a serious referee and likely acceptance after revision. I would not desk-reject it. The main request to the authors should be: give a complete proof of Lemma 7, fix the matching runtime citation, and double-check the dependence issues in the cycle-breaking analysis. I'd bring this to a reading group; the gap in Lemma 7 is a good discussion point, and the rest is instructive.","headline":"A real new problem and a plausible 16/47 ratio, but Lemma 7's proof is incomplete and the weighted-matching runtime is mis-cited; both are fixable.","tokens_in":25672,"tokens_out":2028,"would_cite":true,"duration_ms":19342,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68W20","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces the perfect fair-triangle packing problem, proves it NP-hard even with equal red and blue counts, and gives deterministic 1/3 and randomized (16/47 - epsilon) polynomial-time approximation algorithms.","keywords":["perfect fair-triangle packing","fair clustering","maximum-weight triangle packing","approximation algorithm","randomized algorithm","NP-hardness","maximum-weight matching","[1,2]-factor"],"falsifier":"Enumerate the random cycle-breaking process on a 6-cycle with unit-weight edges: 6 choices of the first edge times the fair coin for the extra deletion give 12 equally likely outcomes; count vertices of degree exactly 1 across all outcomes. If the average is not exactly 1/2 for every even cycle length, Lemma 7 fails and the 16/47 bound collapses; this enumeration also reveals directly whether the two edges incident to a vertex can both be deleted.","tokens_in":24651,"feed_emoji":"📐","tokens_out":11467,"duration_ms":91876,"temperature":0.7,"pith_summary":"The paper introduces a new optimization problem, the perfect fair-triangle packing problem (PFTP): in an edge-weighted complete graph whose 3n vertices are colored red or blue, partition the vertices into n triangles, each containing both colors, while maximizing total edge weight. It establishes that PFTP is NP-hard even in the balanced case where the input has exactly n red and 2n blue vertices. On the positive side, it gives a deterministic matching-based 1/3-approximation algorithm running in O($n^{3}$) time and a randomized (16/47 - epsilon)-approximation algorithm running in O($n^{4}$) time for any fixed small epsilon > 0. The randomized algorithm works by taking a maximum-weight [1,2]-factor of the bichromatic edges, randomly breaking its even cycles into odd alternating paths, and then combining path packings with maximum-weight matchings to build five candidate perfect packings, the best of which is returned. A reader should care because this is the first provable polynomial-time approximation guarantee for the fair version of triangle packing, a natural blend of fair clustering and maximum-weight triangle packing.","feed_headline":"Approximate NP-hard fair-triangle packing to 16/47","feed_subtitle":"A randomized O(n^4) algorithm packs every vertex into red-blue triangles, guaranteed within 16/47 - epsilon of optimal.","key_machinery":"The load-bearing object is the maximum-weight [1,2]-factor F of the bichromatic edge set G_x, a spanning subgraph in which every vertex has degree 1 or 2. Because the bichromatic edges of any optimal packing form such a factor, F is guaranteed to carry at least as much weight as the optimal bichromatic set. Components of F are alternating paths and even alternating cycles; the algorithm removes a small weight from long components so that all remaining components are short, then partitions X into five types by component membership. The random cycle-breaking step (Lemma 7) is the key probabilistic mechanism: each even cycle is broken independently into odd alternating paths in a way that preserves 3/4 of its edge weight and gives each vertex degree exactly 1 with probability 1/2. Lemmas 5 and 6 then convert any vertex-covering collection of alternating paths (or of odd alternating/special paths) into a perfect fair-triangle packing while retaining at least 2/3 of the path weight, and the affine combination in Theorem 3 balances the five candidate packings to reach 16/47.","core_discovery":"The central claim is that PFTP, although NP-hard, admits constant-factor polynomial-time approximations with a structured algorithm. In the deterministic construction, the optimal packing's red edges form a red matching of size r-n and its blue edges form a blue matching of size 2n-r, while its bichromatic edges form n disjoint 2-paths; each of these sub-structures can be approximated separately by maximum-weight matchings, yielding a 1/3-ratio packing. The randomized construction observes that the bichromatic edges of any optimal solution form a [1,2]-factor, so a maximum-weight [1,2]-factor F carries at least the optimal bichromatic weight. After discarding an epsilon fraction of the weight of very long components, the algorithm classifies all bichromatic edges into five types according to which components of F their endpoints lie in, and builds four packings T1,...,T4, each tailored to a class of edges, using dynamic programming, random cycle-breaking, and maximum-weight matchings. Combined with the deterministic packing T0, the heaviest of the five has expected weight at least (16/47 - epsilon) times the optimum.","pith_inferences":["The five-type decomposition suggests a stress test: construct instances whose optimal bichromatic weight is concentrated in one of the five classes, and check that the corresponding candidate packing T_i contributes the predicted share; this would empirically confirm the balancing coefficients in Theorem 3.","The random cycle-breaking primitive is stated for triangle packing, but the same even-cycle-to-odd-paths transformation could be applied to the fair k-cycle and fair (k-1)-path packing variants the conclusion lists, once analogues of Lemmas 5 and 6 are proved for longer paths.","Derandomization of the cycle-breaking step, for example by trying all choices of the first edge in each cycle, would turn the expected (16/47 - epsilon) guarantee into a deterministic one, at the price of a higher polynomial running time."],"forward_implications":["PFTP is NP-hard even when the numbers of red and blue vertices are equal, so no polynomial-time exact algorithm exists unless P = NP.","Every valid instance (with n <= r <= 3n/2 red vertices) can be solved approximately in polynomial time: a deterministic O(n^3) 1/3-approximation and a randomized O(n^4) (16/47 - epsilon)-approximation.","The randomized algorithm's ratio is about 0.340, which beats 1/3 for sufficiently small epsilon, and it does so without relying on weighted 3-set packing, which the paper shows cannot be applied directly when r > n.","The deterministic packing alone establishes that a simple combination of maximum-weight red, blue, and bichromatic matchings already achieves a constant 1/3 ratio."],"supporting_citations":[{"why":"supplies the NP-completeness of 3-dimensional matching and of partition into triangles used in the Theorem 1 reduction.","marker":"[15]"},{"why":"provides the [f,g]-factor technique used to compute maximum-weight size-k matchings and the [1,2]-factor F that carries the randomized algorithm.","marker":"[14]"},{"why":"supplies the random cycle-breaking argument behind Lemma 10 and the prior triangle-packing approximation baseline.","marker":"[16]"},{"why":"provides the probability bound of Lemma 8 on endpoints of paths in randomly broken cycles.","marker":"[20]"},{"why":"gives the O(sqrt(|V||E|)) general-graph maximum matching algorithm used in the time bounds for T2, T3, and T4.","marker":"[18]"},{"why":"supplies the efficient implementation of the blossom maximum-matching algorithm cited for the matching subroutine in Lemma 1.","marker":"[13]"}],"fun_headline_variants":["Fair-triangle packing: from 1/3 to 16/47 via randomization","Beat 1/3: randomized 16/47-approx for fair-triangle packing","Randomized algorithm achieves 16/47-approx for perfect fair-triangle packing","Fair-triangle packing: deterministic 1/3, randomized 16/47","NP-hard fair-triangle packing approximated to 16/47 - epsilon"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The randomized analysis rests on Lemma 7's assertion that after the random cycle-breaking each vertex has degree exactly 1 with probability 1/2; the proof derives this from the two incident edges each surviving with probability 3/4, but those two survival events are dependent, so the stated derivation needs a full case analysis before the later lemmas can be considered established.","fun_headline_variants_meta":{"raw":{"variants":["Fair-triangle packing: from 1/3 to 16/47 via randomization","Beat 1/3: randomized 16/47-approx for fair-triangle packing","Randomized algorithm achieves 16/47-approx for perfect fair-triangle packing","Fair-triangle packing: deterministic 1/3, randomized 16/47","NP-hard fair-triangle packing approximated to 16/47 - epsilon"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000772,"raw_usage":{"total_tokens":3455,"prompt_tokens":1021,"completion_tokens":2434,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":2327}},"tokens_in":637,"tokens_out":2434,"duration_ms":13755,"temperature":1.0,"reasoning_tokens":2327,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:27:23.513812+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate the random cycle-breaking process on a 6-cycle with unit-weight edges: 6 choices of the first edge times the fair coin for the extra deletion give 12 equally likely outcomes; count vertices of degree exactly 1 across all outcomes. If the average is not exactly 1/2 for every even cycle length, Lemma 7 fails and the 16/47 bound collapses; this enumeration also reveals directly whether the two edges incident to a vertex can both be deleted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the NP-completeness of 3-dimensional matching and of partition into triangles used in the Theorem 1 reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the [f,g]-factor technique used to compute maximum-weight size-k matchings and the [1,2]-factor F that carries the randomized algorithm."},{"cited_title":"Hassan and S","cited_arxiv_id":null,"evidence_quote":"supplies the random cycle-breaking argument behind Lemma 10 and the prior triangle-packing approximation baseline."},{"cited_title":"Tanahashi and Z.-Z","cited_arxiv_id":null,"evidence_quote":"provides the probability bound of Lemma 8 on endpoints of paths in randomly broken cycles."},{"cited_title":"Micali and V","cited_arxiv_id":null,"evidence_quote":"gives the O(sqrt(|V||E|)) general-graph maximum matching algorithm used in the time bounds for T2, T3, and T4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the efficient implementation of the blossom maximum-matching algorithm cited for the matching subroutine in Lemma 1."}],"review_version":1}