Pith. sign in

REVIEW 2 major objections 3 minor 25 references

Approximation Algorithms for Perfect Fair-Triangle Packing

T0 review · 2 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2608.07674 v1 pith:3GWIC4AZ submitted 2026-08-07 cs.DS

Mingyang Gong , Zhi-Zhong Chen , Brendan Mumey This is my paper · ORCID
classification cs.DS MSC 68W2568W2005C70
keywords perfectfair-trianglepackingfairclusteringmaximum-weighttriangleapproximationalgorithmrandomizedNP-hardnessmatching[12]-factor
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [Section 5.4, Lemma 7] 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.
  2. [Section 5.5, Lemmas 11, 13, 14] 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.
minor comments (3)
  1. [Section 5.8, Theorem 3] 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.
  2. [Section 5.5, Lemma 10] 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.
  3. [Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No material circularity: the approximation guarantees are derived from explicit constructions, fresh combinatorial lemmas, and convex combinations, not from fitted inputs or self-referential definitions.

full rationale

The derivation chain for both algorithms is self-contained and non-circular. The 1/3-approximation is obtained by lower-bounding two independently constructed packings (matching-based T0 and bichromatic-matching T1) against the same optimal packing T*, then taking a weighted average; nothing is fitted to the optimum and no quantity is defined in terms of the target. The randomized 16/47 algorithm similarly combines lower bounds from Lemmas 4, 11, 13, and 14 on packings built from a maximum-weight [1,2]-factor, a random cycle-breaking procedure, and maximum-weight matchings; the final coefficient algebra in Theorem 3 is a convex combination of these bounds, and the lower bounds themselves are proved from the structure of an optimal packing via matching arguments. The only citation to the authors' own prior work is Lemma 8 [20], but the lemma's proof is reproduced in the manuscript with a case analysis over c mod 4, so the load-bearing endpoint-probability bound does not reduce to an unverified self-citation. Lemma 7's proof of Pr[d_{C1}(u)=1] = 1/2 has a dependency argument that is incomplete as written, since it does not explicitly rule out the both-incident-edges-deleted case in the displayed implication; however, this is a correctness gap in a lemma about a concrete random process, not a circularity, because the probability is neither assumed as an input nor fitted to the final approximation ratio. No definition is self-referential, no known result is merely renamed, and no parameter is fit to the claimed output, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The algorithms introduce no fitted constants, no new physical entities, and no empirical parameters. The only introduced object is the problem definition itself (fair triangle, PFTP), which is a modeling choice rather than a postulated entity. All numerical constants in the approximation ratios are derived from the proofs, not fitted.

assumptions (5)
  • domain assumption Edge weights are nonnegative (Section 2, 'Suppose that each edge of G has a nonnegative weight').
    All weight-loss arguments (deleting low-weight matchings, completing paths with arbitrary edges) rely on never gaining negative weight.
  • domain assumption The input satisfies n <= r <= 3n/2, stated in Problem 1.
    This is the exact feasibility range for the existence of a perfect fair-triangle packing; all algorithms and counting lemmas assume it.
  • standard math Maximum-weight size-k matching and maximum-weight [1,2]-factor can be computed in polynomial time (Lemma 1 and [13,14]).
    Used as black-box subroutines in Approx1 and Approx2; not reproved for the weighted case except for the size-k reduction.
  • standard math 3-dimensional matching is NP-complete ([15]).
    Basis of the NP-hardness reduction in Theorem 1.
  • standard math Every subgraph of maximum degree at most 2 can be edge-partitioned into two matchings (used in Lemma 2).
    Justifies the 1/2 bound on w(M_i) relative to w(X*_i).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximation Algorithms for Perfect Fair-Triangle Packing." pith.science (2026). https://pith.science/paper/3GWIC4AZ

@misc{pith2026260807674,
  author       = {Pith},
  title        = {Pith review of: Approximation Algorithms for Perfect Fair-Triangle Packing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3GWIC4AZ}},
  note         = {Machine review of arXiv:2608.07674}
}
abstract

In this paper, we study the {\em perfect fair-triangle packing} problem (abbreviated as PFTP), which incorporates the fairness criterion from {\em fair clustering} into the {\em maximum-weight triangle packing} problem. Specifically, the input is an edge-weighted complete graph $G = (V, E)$ with $|V| = 3n$, where each vertex is colored red or blue. A {\em fair triangle} is a triangle containing vertices of both colors. PFTP asks for a partition of $V$ into $n$ fair triangles such that the total edge weight is maximized. To the best of our knowledge, this is the first paper to study PFTP. PFTP is NP-hard. Our main contributions are a deterministic $\frac 13$-approximation algorithm running in $O(n^3)$ time and an improved randomized $(\frac {16}{47}-\epsilon)$-approximation algorithm running in $O(n^4)$ time, where $\epsilon > 0$ is a fixed small constant. The deterministic algorithm is matching-based whereas the randomized algorithm employs several additional techniques, including maximum-weight $[1, 2]$-factor, a random cycle-breaking procedure, and maximum-weight matchings. Keywords: Triangle packing; fairness; approximation algorithms; randomized algorithms

Figures

Figures reproduced from arXiv: 2608.07674 by the authors.

Figure 1
Figure 1. A red-dominant triangle (left) and a blue-dominant triangle (right). All solid edges are [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The gadget constructed for a given triple [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. A simple approximation algorithm for PFTP. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: The different types of edges in X∗ . In the graph, F consists of two 4-cycles, two 2-paths, and one 4-path. For each i ∈ {1, . . . , 5}, the dashed edge ei is in X∗ \ E(F) and is of Type-i. are colored red, blue, and red (respectively, blue, red, and blue). A fair (1, …
Figure 5
Figure 5. Figure 5: Dynamic-programming algorithm for computing [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Breaking the cycles in F shown in [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]
Figure 7
Figure 7. Figure 7: Breaking a cycle in C at random. Let C1 be the graph obtained from C by breaking the cycles in C as described above. As noted above, each connected component of C1 is an odd alternating path. Lemma 7 Let C be a cycle in C. For each e ∈ E(C), Pr[e ∈ E(C1)] = 3 4 . Moreo…
Figure 8
Figure 8. Figure 8: All possible cases when c = 6 and dC1 (u) = dC1 (t) = 1. Each case occurs with probability 1 12 . The dashed edges are removed from C by the algorithm in [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 9
Figure 9. Figure 9: An example C, C1, M′ 2 , and C2. C consists of the two 6-cycles, C1 is obtained from C by deleting the dashed edges, M′ 2 = {e, e′}, and C2 is obtained from C1 by adding e and e ′ . Note that C2 is a 12-cycle. Clearly, each cycle in C2 contains at least two edges of M′…
Figure 10
Figure 10. Figure 10: Computing the second perfect fair-triangle packing [PITH_FULL_IMAGE:figures/full_fig_p020_10.png]
Figure 11
Figure 11. Figure 11: An illustration of the construction of P1 and M′ 3 . The two 3-paths on the left are obtained by breaking the cycles in [PITH_FULL_IMAGE:figures/full_fig_p021_11.png]
Figure 12
Figure 12. Figure 12: Computing the third fair-triangle packing [PITH_FULL_IMAGE:figures/full_fig_p022_12.png]
Figure 13
Figure 13. Figure 13: An illustration of the construction of P2 and M′ 4 . The two 3-paths on the left are obtained by breaking the cycles in [PITH_FULL_IMAGE:figures/full_fig_p023_13.png]
Figure 14
Figure 14. Figure 14: Algorithm for computing T4: Input: G, C, and P; 1. Perform the first two steps in [PITH_FULL_IMAGE:figures/full_fig_p023_14.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [18]

    Micali and V

    S. Micali and V. V. Vazirani. AnO( p |V||E|) algorithm for finding maximum matching in general graphs. InProceedings of FOCS 1980, pages 17–27, 1980

    work page 1980

  2. [20]

    Tanahashi and Z.-Z

    R. Tanahashi and Z.-Z. Chen. A deterministic approximation algorithm for maximum 2-path packing.IEICE Transactions on Information and Systems, E93-D(2):241–249, 2010

    work page 2010

  3. [13]

    H. N. Gabow. An efficient implementation of edmonds’ algorithm for maximum matching on graphs.Journal of the Association for Computing Machinery, 23:221–234, 1976

    work page 1976

  4. [14]

    H. N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. InProceedings of STOC 1983, pages 448–456, 1983

    work page 1983

  5. [1]

    Bandyapadhyay, T

    S. Bandyapadhyay, T. Chen, Z. Friggstad, and M. Jamshidian. A constant-factor approxima- tion for pairwise fairk-center clustering. InProceedings of IPCO 2025, LNCS 15620, pages 43–57, 2025

    work page 2025

  6. [2]

    A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering

    S. Bandyapadhyay, E. Chlamt´ aˇ c, Z. Friggstad, M. Jamshidian, Y. Makarychev, and A. Vak- ilian. A polynomial-time approximation for pairwise fairk-median clustering, 2025.https: //arxiv.org/pdf/2405.10378

    work page Pith review arXiv 2025

  7. [3]

    S. K. Bera, D. Chakrabarty, N. Flores, and M. Negahbani. Fair algorithm for clustering. In Proceedings of 33rd Conference on Neural Information Processing Systems, pages 4955–4966, 2019

    work page 2019

  8. [4]

    I. O. Bercea, M. Groß, S. Khuller, A. Kumar, C. R¨ osner, D. R. Schmidt, and M. Schmidt. On the cost of essentially fair clusterings. InProceedings of APPROX/RANDOM 2019, LIPIcs 145, pages 18:1–18:22, 2019

    work page 2019

Show all 25 references
  1. [5]

    Chen, Z.-Z

    Y. Chen, Z.-Z. Chen, G. Lin, L. Wang, and A. Zhang. A randomized approximation algorithm for metric triangle packing.Journal of Combinatorial Optimization, 41:12–27, 2021

    2021

  2. [6]

    Z.-Z. Chen, R. Tanahashi, and L. Wang. An improved randomized approximation algorithm for maximum triangle packing.Discrete Applied Mathematics, 157:1640–1646, 2009

    2009

  3. [7]

    an improved randomized approximation algorithm for maximum triangle packing

    Z.-Z. Chen, R. Tanahashi, and L. Wang. Erratum to “an improved randomized approximation algorithm for maximum triangle packing” [discrete appl. math. 157 (2009) 1640–1646].Discrete Applied Mathematics, 158:1045–1047, 2010. 25

    2009

  4. [8]

    Chierichetti, R

    F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In Proceedings of 31st Conference on Neural Information Processing Systems, pages 5036–5044, 2017

    2017

  5. [9]

    Chleb ´ ık and J

    M. Chleb ´ ık and J. Chleb ´ ıkov´ a. Complexity of approximating bounded variants of optimization problems.Theoretical Computer Science, 354:320–338, 2006

    2006

  6. [10]

    M. Cygan. Improved approximation for 3-dimensional matching via bounded pathwidth local search. InProceedings of FOCS 2013, pages 509–518, 2013

    2013

  7. [11]

    Dickerson, S

    J. Dickerson, S. A. Esmaeili, J. Morgenstern, and C. J. Zhang. SoK: Fair clustering: Cri- tique, caveats, and future directions. InProceedings of 2025 IEEE Conference on Secure and Trustworthy Machine Learning, pages 698–713, 2025

    2025

  8. [12]

    F¨ urer and H

    M. F¨ urer and H. Yu. Approximating thek-set packing problem by local improvements. In Proceedings of ISCO 2014, volume 8596, pages 408–420, 2014

    2014

  9. [15]

    M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, San Francisco, 1979

    1979

  10. [16]

    Hassan and S

    R. Hassan and S. Rubinstein. An approximation algorithm for maximum triangle packing. Discrete Applied Mathematics, 154:971–979, 2006

    2006

  11. [17]

    V. Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete.Information Processing Letters, 37:27–35, 1991

    1991

  12. [19]

    Bagheri Nezhad, S

    S. Bagheri Nezhad, S. Bandyapadhyay, and T. Chen. Polynomial-time constant-approximation for fair sum-of-radii clustering. InProceedings of ESA 2025, LIPIcs 351, pages 62:1–16, 2025

    2025

  13. [21]

    Thiery and J

    T. Thiery and J. Ward. An improved approximation for maximum weightedk-set packing. In Proceedings of SODA 2023, pages 1138–1162, 2023

    2023

  14. [22]

    J. M. M. van Rooij, M. E. van Kooten Niekerk, and H. L. Bodlaender. Partition into triangles on bounded degree graphs.Theory of Computing Systems, 52:687–718, 2013

    2013

  15. [23]

    van Zuylen

    A. van Zuylen. Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems.Discrete Applied Mathematics, 161(13-14):2142– 2157, 2013. 26

    2013

  16. [24]

    Williamson and D.B

    D.P. Williamson and D.B. Shmoys.The design of approximation algorithms. Cambridge University Press, 2011

    2011

  17. [25]

    Zhao and M

    J. Zhao and M. Xiao. A deterministic approximation algorithm for metric triangle packing. Theoretical Computer Science, 1010:Article 114699, 2024. A A table for notations Table 1: Important notations and their meanings Notations Their meanings X The set of bichromatic edges in...

    2024

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.