{"id":"adb1aa59-af11-4c76-a028-302a2b38bd61","arxiv_id":"2504.15082","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":8,"one_line_summary":"PEM-Color combines Harris Hawks, Bee Colony, and Teaching-Learning optimizers in parallel for graph coloring, but inconsistent tables and a missing baseline mean the claimed superiority over 13 algorithms is not supported.","lead":"This paper presents PEM-Color, a parallel algorithm that runs three nature-inspired optimization methods on separate processors and keeps the best graph coloring it finds. Its central claim, that it outperforms 13 prior algorithms, is contradicted by the paper's own tables, which show it tying or losing on nearly every instance.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's own tables contradict the central claim: Table 3 and Table 4 give different PEM-Color results for identical instances, and Table 4 shows several state-of-the-art algorithms beating PEM-Color.","rationale":"Read in good faith, the paper's central intended claim is that the island-parallel ensemble PEM-Color obtains best-known or better colorings on DIMACS large graphs and outperforms 13 published algorithms. For that claim to hold, two things have to be true: Table 3 must be a valid record of PEM-Color's outcomes, and Table 4 must compare those same outcomes against the listed competitors. The manuscript's own numbers violate both conditions. The four largest instances have different PEM-Color entries in the two tables, and the aggregate total 2040 cited in the text is the sum of the Table 4 row, not the Table 3 row, whose sum is 1994. That is not a single-cell typo; it means the result table and the comparison table come from different runs or different reporting standards. If Table 3 is the real result, then k* is wrong (153 should be at least as low as MACOL's 148; 280 as low as 272), and the '37/43' count is misleading. If Table 4 is the real result, the abstract's 'outperforms 13 state-of-the-art algorithms' is false. Either way the central claim is unsupported. I also note the ensemble contribution is not tested against its component metaheuristics and no code is released, so the paper offers no independent check. Because this is an internal inconsistency rather than a disagreement with external consensus, it goes directly to soundness of the reported results. I agree with the reader's REJECT; the only nuance is that Table 3's k-values are not necessarily 'below the true best-known'—the k* column itself appears stale—but the incompatibility between Tables 3 and 4 is the decisive problem.","tokens_in":19185,"tokens_out":14022,"duration_ms":107273,"concrete_test":"Re-run PEM-Color on C2000.5 and C4000.5 with the Table 1 settings, validate the best reported k-colorings with an independent proper-coloring checker, and compare with both Table 3 (148, 272) and Table 4 (153, 301). In parallel, check whether the Table 4 minimum competitor values (148, 272) match the DIMACS best-known values that the k* column is supposed to report. If the reproduced k matches Table 3, Table 4 and the comparison claims are wrong; if it matches Table 4, Table 3 and the '37/43' claim are wrong; if it matches neither, the reported results are not reproducible.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Table 3 and Table 4 cannot both be reports of the same PEM-Color runs. For C2000.5, Table 3 gives k=148 with 20/20 hits while Table 4 lists PEM-Color as 153; for C4000.5, Table 3 gives 272 but Table 4 lists 301; for DSJC500.5, Table 3 gives 48 but Table 4 lists 49; for DSJC1000.9, Table 3 gives 223 but Table 4 lists 226. The narrative after Table 3 compounds the conflict: it says 2040 colors were used against a total best-known sum of 2003, but the sum of the Table 3 k column is 1994, whereas 2040 is exactly the sum of the Table 4 PEM-Color row. The two tables therefore report different experimental outputs. On Table 4 itself, PEM-Color is not state-of-the-art: C2000.5 (153) loses to EVOCOL (151) and MACOL (148); DSJC1000.5 (84) loses to HEA/MMT/EVOCOL/MACOL (83); DSJC1000.9 (226) loses to MACOL (223); DSJR500.5 (125) loses to PCNS (123), MMT (122), EVOCOL (124), and MACOL (122); R1000.5 (240) loses to MMT (234). The abstract claim that PEM-Color outperforms 13 state-of-the-art algorithms is unsupported by the paper's own comparison table. The k* column is also suspect: C2000.5 and C4000.5 are listed as 153 and 280 even though Table 4 contains MACOL values of 148 and 272. No code or raw outputs are provided, so these are not distinguishable as simple typos without an independent check.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PEM-Color, an island-parallel ensemble metaheuristic that combines Harris Hawk Optimization, Artificial Bee Colony, and Teaching-Learning-Based Optimization with a TabuCol local search to solve large DIMACS graph coloring instances using MPI. The authors report results for 43 instances, claim a near-linear speed-up on 64 processors, and state in the abstract and introduction that PEM-Color outperforms 13 state-of-the-art algorithms and achieves the best known solutions in 37 of 43 instances.","tokens_in":19679,"tokens_out":7133,"duration_ms":53846,"significance":"If the reported results were reproducible, the paper would offer a useful contribution to parallel metaheuristics for graph coloring, and the island-parallel ensemble design is a plausible way to combine complementary search strategies. The authors also correctly identify that the GCP literature lacks parallel ensemble approaches based on these three metaheuristics. However, the manuscript's central empirical claims are not supported by its own tables: Table 3 and Table 4 report different PEM-Color outcomes for the same instances, the k* column contains values contradicted by the paper's own comparison table, and the claimed superiority over 13 state-of-the-art algorithms is contradicted by Table 4, where PEM-Color never achieves the unique best value on any instance. No code, raw outputs, or verifier for the colorings are provided, so the contradictions cannot be resolved from the manuscript alone.","major_comments":[{"comment":"The two main result tables are irreconcilable for the same instances. Table 3 reports k=148 for C2000.5 while Table 4 lists PEM-Color as 153; Table 3 reports k=272 for C4000.5 while Table 4 lists 301; Table 3 reports k=48 for DSJC500.5 while Table 4 lists 49; and Table 3 reports k=223 for DSJC1000.9 while Table 4 lists 226. The narrative in §4.2 states that 2040 colors were used with a best-known total of 2003, but the sum of the Table 3 k column is 1994, whereas 2040 is exactly the sum of the Table 4 PEM-Color row. Because the central claim of 'best results in 37 out of 43' depends on which table is accepted, the manuscript as submitted does not support its abstract's claims.","section":"§4.2, Table 3 vs. §4.3, Table 4"},{"comment":"The claim that PEM-Color 'outperforms 13 state-of-the-art algorithms' is contradicted by the paper's own comparison. In Table 4, PEM-Color ties or loses to at least one comparator on every row and never achieves the best value by itself: C2000.5 loses to Evocol (151) and MACOL (148); DSJC500.5 loses to VSS, Foopar, HEA, AMACOL, MMT, Evocol, and MACOL (48); DSJC1000.5 loses to HEA, MMT, Evocol, and MACOL (83); DSJR500.5 loses to PCNS, MMT, MIPS, Evocol, and MACOL (122); R1000.5 loses to MMT (234). Thus, even setting aside the Table 3/Table 4 conflict, the comparative statement in the abstract and introduction is not supported by the evidence the authors present.","section":"Abstract and §4.3, Table 4"},{"comment":"The best-known values listed in Table 3 are internally inconsistent with Table 4. Table 3 lists k*=153 for C2000.5, but Table 4 reports MACOL at 148 and Evocol at 151; Table 3 lists k*=280 for C4000.5, but Table 4 reports MACOL at 272; Table 3 lists k*=49 for DSJC500.5, but Table 4 reports six algorithms at 48. If the Table 3 values are correct, then the paper reports new best-known colorings (e.g., C2000.5 at 148, DSJC500.5 at 48, DSJC1000.9 at 223) and must flag them as such, but it never does. If they are incorrect, the '37 more colors' calculation and the '37 out of 43' claim are not meaningful.","section":"Table 3, k* column"},{"comment":"The strong and linear scalability claim is not backed by experimental evidence. The section asserts an 'almost linear speed-up' and that MPI overhead is 'not more than 5%', but it reports no speed-up curve, no strong/weak scaling experiments, and no comparison of parallel execution time against a sequential implementation of the same algorithm. The observation that 64 processors perform 1,280,000 fitness evaluations while each processor performs 20,000 is an aggregate throughput statement that follows directly from the experimental design, not a speed-up result, and it does not control for solution quality or communication cost.","section":"§4.4, scalability and speed-up analysis"}],"minor_comments":[{"comment":"The sentence 'We used 2040 colors to paint all these graphs in Table 2' is inconsistent with the content: Table 2 is the small-instance table, and the 2040 total matches the Table 4 PEM-Color row, not the Table 3 column. This typo adds to the confusion caused by the table discrepancies.","section":"§4.2"},{"comment":"Section 3.1 states that parameters are 'randomly selected within the defined ranges', but the paper never specifies these ranges, and Table 1 only lists fixed values or qualitative descriptions (e.g., 'random' for J, 'range of (-1, 1)' for E0). This makes the reported parameter settings not fully reproducible.","section":"Table 1 and §3.1"},{"comment":"DSJC250.5 appears in both Table 2 and Table 3 with the same k=28 but with different average times (10.214 seconds vs. 8.7 seconds). The manuscript does not explain whether these are separate experiments, different stopping conditions, or a reporting error.","section":"Tables 2 and 3"},{"comment":"Several references contain placeholder text '???' for publisher locations (e.g., Alba 2005, Barenboim and Elkin 2013, Jensen and Toft 2011, Talbi 2009), and some bibliographic entries are incomplete. A careful proofreading of the reference list is needed.","section":"References"}],"recommendation":"reject","confidential_remarks":"The inconsistencies between Tables 3 and 4 are so extensive that the reliability of the experimental data is in question. No code or raw outputs are provided that would allow an independent check of whether, for example, the Table 3 value k=148 for C2000.5 is a valid proper coloring. Given that the central 'outperforms 13 state-of-the-art algorithms' claim is contradicted by the paper's own comparison table, I cannot recommend acceptance or even a minor revision. If the authors can supply corrected tables, verified colorings, and reproducible code, a substantially revised manuscript might be worth reconsidering."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the headline claim doesn't survive contact with the paper's own tables. Table 3 and Table 4 give different PEM-Color results for the same DIMACS instances, and Table 4 shows PEM-Color losing to several state-of-the-art methods. The abstract says it outperforms 13 algorithms, but the comparison table says otherwise.\n\nWhat's genuinely new: the specific combination of HHO, ABC, and TLBO in an island-parallel MPI framework, and the first application of HHO to graph coloring. That's a fair contribution, if modest. The related-work survey is broad and correctly cites the most relevant parallel and ensemble metaheuristic work, including the authors' own earlier TLBO-Color and HHO papers.\n\nThe soft spots are serious. For C2000.5, Table 3 reports k=148 with 20/20 hits; Table 4 lists PEM-Color as 153. C4000.5: Table 3 says 272 (0/20 hits), Table 4 says 301. DSJC500.5: 48 vs 49. DSJC1000.9: 223 vs 226. The two tables can't both describe the same runs. The narrative compounds this: it says 2040 colors were used for the large instances and the best-known total is 2003, but the sum of Table 3's k column is 1994, while 2040 is exactly the sum of Table 4's PEM-Color column. That's not a typo; it's two different experimental outputs.\n\nEven taking Table 4 at face value, PEM-Color is not state of the art. MACOL beats it on C2000.5 (148 vs 153), DSJC1000.9 (223 vs 226), and DSJR500.5 (122 vs 125); MMT beats it on R1000.5 (234 vs 240). So the central claim collapses.\n\nThe scalability section never measures wall-clock speedup; it just multiplies fitness evaluations by processor count. No code or raw data are provided, so the better-than-best-known entries in Table 3 (148, 272, 48, 223) cannot be checked. Parameters are reused from prior work, and the ensemble is never compared to its own components, so we don't know if the ensemble adds anything.\n\nRecommendation: desk reject for now. The internal contradiction is load-bearing. A serious revision that reconciles the numbers, provides raw outputs, and drops or rewords the state-of-the-art claim might produce a modest engineering paper, but this version doesn't deserve referee time.","headline":"The paper's central claim is contradicted by its own tables, and the results as reported cannot be trusted without a full redo.","tokens_in":20164,"tokens_out":3324,"would_cite":false,"duration_ms":27960,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","68T20","68W10"],"pacs":[],"model":"deepseek-v4-flash","headline":"An island-parallel ensemble of three metaheuristics, polished by tabu search, matches or beats the best-known color count on 37 of 43 large benchmark graphs and scales almost linearly to 64 processors.","keywords":["graph coloring","ensemble metaheuristic","island parallel","Harris Hawk Optimization","Artificial Bee Colony","Teaching-Learning-Based Optimization","TabuCol","MPI parallelization"],"falsifier":"Independently verify the reported colorings, especially the four where Table 3 shows a count below the stated best-known value (C2000.5 at 148 colors, C4000.5 at 272, DSJC500.5 at 48, DSJC1000.9 at 223): check every edge to confirm no two endpoints share a color, and reconcile the different values Table 4 lists for the same instances (301, 49, and 226). If any adjacent pair shares a color, or if the Table 4 values are the real outputs, the claimed improvement over best-known solutions is not established.","tokens_in":19009,"feed_emoji":"🎨","tokens_out":12230,"duration_ms":101413,"temperature":0.7,"pith_summary":"Graph coloring asks for the fewest colors that label the vertices of a graph so that adjacent vertices never share a color, and large instances are NP-hard in practice, so heuristic search is the norm. This paper proposes PEM-Color, an island-parallel ensemble that runs three recent metaheuristics — Harris Hawk Optimization, Artificial Bee Colony, and Teaching-Learning-Based Optimization — on separate groups of processors, with the tabu-search procedure TabuCol refining every candidate solution. The paper's central claim is that the ensemble matches or beats the best-known color counts on 37 of 43 large benchmark instances and does so in practical wall-clock times, from under a second on easy instances to about half an hour on the hardest, while gaining an almost linear speed-up as processors are added. A sympathetic reader would care because this is presented as the first ensemble-of-metaheuristics treatment of graph coloring, and it offers evidence that algorithm diversity plus parallel hardware can compete with dedicated single-algorithm solvers that are often allowed days of runtime.","feed_headline":"Parallel ensemble beats best-known colorings on 37 of 43","feed_subtitle":"Three metaheuristics on 64 processors match or beat best-known results in minutes, not days.","key_machinery":"The load-bearing mechanism is the island-parallel ensemble itself: 64 Message Passing Interface (MPI) processes form one master and 63 slaves, partitioned into three groups of 21, with each group running one metaheuristic (Harris Hawk Optimization, Artificial Bee Colony, or Teaching-Learning-Based Optimization) on a population of 20 candidate colorings, and each slave seeded differently so the same metaheuristic explores many parameter settings at once. TabuCol acts as a local-search polish applied to every candidate after each generation. The master receives only the best solution from each slave at generation boundaries, keeping communication near zero, which is what allows near-linear speed-up. The ensemble exploits the no-free-lunch observation that no single metaheuristic dominates all instances: different islands are expected to lead on different graphs, and the master's simple choose-the-best rule selects the winner.","core_discovery":"On its own terms, the paper's discovery is that three complementary population-based search methods — Harris Hawk Optimization, Artificial Bee Colony, and Teaching-Learning-Based Optimization — can be wrapped in a master-slave parallel ensemble, with the TabuCol local search polishing every candidate, so that the combined search is at least as good as thirteen published graph-coloring algorithms on the standard large benchmark instances. The design runs 63 slaves in three groups of 21, one group per metaheuristic, each slave using its own random seed; the master collects only the best solution from each slave at generation boundaries. The paper reports exact matches of the best-known color counts on all 19 small instances, best-known or better counts on 18 of 24 large instances, and a total used-color count only 1.84 percent above the sum of the best-known values for the large set, together with an almost linear speed-up in fitness evaluations on 64 processors. If these numbers hold, the contribution is a recipe for turning metaheuristic diversity into state-of-the-art graph coloring without letting communication overhead eat the parallelism.","pith_inferences":["If the Table 3 entries that are lower than the stated best-known values (for instance 148 colors on C2000.5 against a stated best of 153) are valid proper colorings, they would be new record upper bounds; the paper never says so explicitly, and independent verification is the natural next step.","The same island-ensemble wrapper could be lifted onto other NP-hard problems the paper names, such as traveling salesman or maximum clique, because the wrapper only needs a fitness function and a local-search polisher; a port would test whether ensemble diversity, not the specific metaheuristics, is the active ingredient.","The current design gives each metaheuristic the same number of islands regardless of instance difficulty; an adaptive scheduler that reassigns processors to the metaheuristic making the fastest progress is a testable extension that could improve both time and final color count.","The speed-up evidence is presented as a count of fitness evaluations rather than as a measured wall-clock scaling curve; running the same instances with 8, 16, 32, and 64 processors would confirm whether communication overhead really stays under the reported 5 percent."],"forward_implications":["If the 37-of-43 result holds, PEM-Color sits with the strongest published graph-coloring algorithms on large instances while using a fraction of their wall-clock time.","The almost linear speed-up means the ensemble's 64 processors deliver roughly 64 times as many fitness evaluations in the same wall-clock time, so buying more cores is a direct way to shorten the search.","Because different islands run different metaheuristics with different random seeds, a graph that stalls one metaheuristic can still be solved by another island, which is a practical hedge against the no-free-lunch principle.","Since every candidate is polished by TabuCol, the ensemble's advantage is best understood as a diversification layer on top of a strong tabu-search core, not as a replacement for local search."],"supporting_citations":[{"why":"Defines Harris Hawk Optimization, whose exploration and exploitation phases PEM-Color adapts to graph coloring.","marker":"Heidari et al., 2019"},{"why":"Defines Artificial Bee Colony, one of the three ensemble members and the source of the employed, onlooker, and scout bee population structure.","marker":"Karaboga and Basturk, 2008"},{"why":"Defines Teaching-Learning-Based Optimization, the parameter-free teacher and learner search used as the third ensemble member.","marker":"Rao et al., 2011"},{"why":"Introduces the TabuCol tabu-search move that PEM-Color applies to every candidate solution after each generation.","marker":"Hertz and Werra, 1987"},{"why":"Contributes the memetic and parallel TLBO coloring algorithms that PEM-Color generalizes and uses as a comparison baseline.","marker":"Dokeroglu and Sevinc, 2021"},{"why":"Supplies the island-parallel Harris Hawks framework that PEM-Color extends to multiple cooperating metaheuristics.","marker":"Dokeroglu and Sevinc, 2022"},{"why":"Provides the closest prior parallel ensemble of metaheuristics, which PEM-Color moves from GPU computation to MPI islands.","marker":"Hijazi et al., 2021"},{"why":"Gives the no-free-lunch theorem that motivates running several metaheuristics at once so different instances can be won by different islands.","marker":"Wolpert and Macready, 1997"},{"why":"Defines the benchmark problem suite and supplies the best-known chromatic numbers used for comparison.","marker":"Johnson and Trick, 1996"},{"why":"Presents MACOL, the memetic algorithm the paper identifies as holding the best results on most large instances and a principal baseline for the comparison.","marker":"Lü and Hao, 2010"}],"fun_headline_variants":["Ensemble of three metaheuristics colors large graphs fast","Parallel trio beats 13 rivals on graph coloring benchmark","64-core ensemble matches best-known colorings in minutes","Island-parallel metaheuristic ensemble cuts coloring time nearly linearly","Trio of algorithms color graphs in near-linear parallel speed"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's headline comparison rests on the assumption that every color count it reports in Table 3 is a valid proper coloring and that the best-known values it compares against are correct; if the entries that appear better than the stated best-known values are errors, the claim of best results in 37 out of 43 instances collapses.","fun_headline_variants_meta":{"raw":{"variants":["Ensemble of three metaheuristics colors large graphs fast","Parallel trio beats 13 rivals on graph coloring benchmark","64-core ensemble matches best-known colorings in minutes","Island-parallel metaheuristic ensemble cuts coloring time nearly linearly","Trio of algorithms color graphs in near-linear parallel speed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001057,"raw_usage":{"total_tokens":4464,"prompt_tokens":1003,"completion_tokens":3461,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":3380}},"tokens_in":619,"tokens_out":3461,"duration_ms":21727,"temperature":1.0,"reasoning_tokens":3380,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:33:21.360639+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Independently verify the reported colorings, especially the four where Table 3 shows a count below the stated best-known value (C2000.5 at 148 colors, C4000.5 at 272, DSJC500.5 at 48, DSJC1000.9 at 223): check every edge to confirm no two endpoints share a color, and reconcile the different values Table 4 lists for the same instances (301, 49, and 226). If any adjacent pair shares a color, or if the Table 4 values are the real outputs, the claimed improvement over best-known solutions is not established.","supporting_citations":[{"cited_title":", Mirjalili , S","cited_arxiv_id":null,"evidence_quote":"Defines Harris Hawk Optimization, whose exploration and exploitation phases PEM-Color adapts to graph coloring."},{"cited_title":", Basturk , B","cited_arxiv_id":null,"evidence_quote":"Defines Artificial Bee Colony, one of the three ensemble members and the source of the employed, onlooker, and scout bee population structure."},{"cited_title":", Savsani , V.J","cited_arxiv_id":null,"evidence_quote":"Defines Teaching-Learning-Based Optimization, the parameter-free teacher and learner search used as the third ensemble member."},{"cited_title":", Werra , D.d","cited_arxiv_id":null,"evidence_quote":"Introduces the TabuCol tabu-search move that PEM-Color applies to every candidate solution after each generation."},{"cited_title":", Sevinc , E","cited_arxiv_id":null,"evidence_quote":"Contributes the memetic and parallel TLBO coloring algorithms that PEM-Color generalizes and uses as a comparison baseline."},{"cited_title":", Sevinc , E","cited_arxiv_id":null,"evidence_quote":"Supplies the island-parallel Harris Hawks framework that PEM-Color extends to multiple cooperating metaheuristics."},{"cited_title":", Faris , H","cited_arxiv_id":null,"evidence_quote":"Provides the closest prior parallel ensemble of metaheuristics, which PEM-Color moves from GPU computation to MPI islands."},{"cited_title":", Macready , W.G","cited_arxiv_id":null,"evidence_quote":"Gives the no-free-lunch theorem that motivates running several metaheuristics at once so different instances can be won by different islands."}],"review_version":1}