Pith. sign in

REVIEW 3 major objections 6 minor 51 references

WeGotYouCovered: The Winning Solver from the PACE 2019 Implementation Challenge, Vertex Cover Track

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The winning solver of the 2019 vertex cover challenge is a scheduled portfolio that first shrinks the graph with reduction rules, then alternates two search paradigms, and the paper shows the shrink step is what makes a clique-style…

desk verdict The PACE win is credible and the code is public, but the paper's two headline insights rest on near-duplicate instances and unseeded runs, so the ablation claims are over-sold. read the letter →

arxiv 1908.06795 v2 pith:LSVH3TOH submitted 2019-08-19 cs.DS

Demian Hespe , Sebastian Lamm , Christian Schulz , Darren Strash This is my paper · ORCID
classification cs.DS
keywords minimumvertexcoverkernelizationbranch-and-boundbranch-and-reducelocalsearchmaximumcliqueindependentsetPACE2019
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 claims that the best way to solve hard minimum vertex cover instances exactly is not a single algorithm but a time-scheduled pipeline: aggressively shrink the graph with reduction rules, obtain a strong starting solution by local search, then alternate branch-and-reduce and branch-and-bound search under short and long time limits. The authors show that two techniques borrowed from the complementary maximum clique and maximum independent set problems carry most of the gain. Kernelization lets a state-of-the-art branch-and-bound clique solver, run on the complement graph, solve more than twice as many public instances as it could without reduction, and a local-search starting solution lets branch-and-reduce solve more instances than it could alone. The challenge result is the evidence: the full portfolio solved 82 of 100 public instances and 87 of 100 held-out private instances, ten more than the runner-up. The paper also records a counterintuitive side effect: reductions can occasionally make the kernel harder for branch-and-bound, so a robust solver should search both the kernel and the original graph.

What carries the argument

The load-bearing identity is the complement relation among the three problems: a minimum vertex cover of $G$ is the complement of a maximum independent set, which is a maximum clique in the complement graph. The portfolio combines four mechanisms. Kernelization repeatedly applies data-reduction rules—degree-one removal, vertex folding, an LP-relaxation reduction, and unconfined, twin, funnel, and desk reductions—to shrink the graph while preserving a minimum vertex cover. Iterated local search based on $(1,2)$-swaps finds a high-quality initial cover on the kernel. Branch-and-reduce interleaves the same reductions with branching, mirror and satellite elimination, and lower-bound pruning. MoMC is a branch-and-bound maximum-clique solver using incremental MaxSAT reasoning to prune search, run on the complement graph of both the kernel and the original input. The phase order and time limits (one second for short phases, thirty seconds for the long branch-and-reduce phase, then the remaining budget for branch-and-bound) are what make the portfolio work.

What would settle it

Run the same configurations—plain branch-and-bound, kernelized branch-and-bound, branch-and-reduce with and without a local-search starting solution, and the full portfolio—on a fresh corpus of 100 previously unseen instances that includes dense graphs, under the same 30-minute budget; the central claim would be contradicted if kernelized branch-and-bound no longer solves more instances than branch-and-reduce, or if the portfolio's margin collapses.

Watch

Extended reading notes

Core claim

The central discovery is that kernelization and branch-and-bound compose in a way the vertex cover literature had not demonstrated. On the 100 public instances, plain branch-and-bound solved 30 instances, but the same solver run on the reduced kernel solved 68; branch-and-reduce with reductions but no local search solved 42, and adding a locally searched initial solution raised that to 55. The complete portfolio solved 82 public and 87 private instances within the 30-minute competition limit. The paper claims this is the first time kernelization followed by branch-and-bound is shown to significantly outperform branch-and-reduce, and it explains a necessary detail: the branch-and-bound solver must also be run on the original graph, because the alternative reduction can increase the number of edges and make the kernel harder than the input.

Load-bearing premise

The load-bearing premise is that the 100 public and 100 private benchmark instances, with a fixed 30-minute time limit and hand-tuned phase time limits, stand in for the space of exact vertex cover instances; the paper itself notes that reduction-based techniques rarely work on dense graphs.

Editorial extensions

If this is right

  • Exact minimum vertex cover solvers should be built as pipelines rather than as single algorithms: kernelize, obtain a good initial solution by local search, then let branch-and-reduce and branch-and-bound share the remaining time budget.
  • Because vertex cover, maximum independent set, and maximum clique are complementary, the same pipeline transfers directly to solving maximum clique or maximum independent set on sparse graphs.
  • Kernelization is not always safe for branch-and-bound: since reductions can increase the number of edges, a robust solver should search both the kernel and the original graph unless it can prove the kernel is easier.
  • Branch-and-reduce benefits substantially from a high-quality initial solution produced by local search on the kernel, even though the reduction rules themselves do not depend on it.

Reading between the lines

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

  • Inference: an adaptive kernelizer that only keeps reductions when they do not increase the edge count, or that falls back to the original graph on edge growth, could recover the two documented hard cases without paying for two full searches.
  • Inference: the same portfolio-scheduling idea—kernelize, seed with local search, then time-slice a reduce-heavy and a bound-heavy solver—may transfer to other NP-hard problems that have practical kernelizations and strong branch-and-bound solvers.
  • Inference: the hand-tuned phase time limits suggest a testable extension in which the schedule is learned from instance features on the public corpus and then evaluated on held-out instances, which would measure how much of the win depends on the tuning rather than on the component algorithms.
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

3 major / 6 minor

Summary. The paper presents WeGotYouCovered, the winning solver of the PACE 2019 Implementation Challenge Vertex Cover Track. The solver is a four-phase portfolio: kernelization with an adaptation of Akiba and Iwata's reduction suite, iterated local search on the kernel, branch-and-reduce with an initial solution, and two calls to the MoMC branch-and-bound maximum-clique solver on the complement graph (one on the kernel, one on the original graph). On the 100 public benchmark instances, the full algorithm solves 82; on the 100 private instances it solves 87, beating the second-place solver by 10 instances. The paper's ablations report that RMoMC (kernelization plus MoMC) solves 68 public instances versus 42 for BnR (branch-and-reduce), LSBnR (local search plus BnR) solves 55, and MoMC alone solves 30. The authors draw three qualitative conclusions: kernelization can boost branch-and-bound enough to beat branch-and-reduce, local search can significantly boost branch-and-reduce, and kernelization can sometimes hurt branch-and-bound (instances 131 and 157).

Significance. If supported, the paper's insights are valuable to the exact vertex cover / maximum clique / independent set community: they demonstrate that techniques can be transferred across these equivalent problems and that portfolio design matters for competition-level performance. The paper ships its source code under an open license, reports per-instance results on an external benchmark, and compares fixed algorithm configurations without fitted parameters, which is a strength. The PACE 2019 win itself is credible and is a useful data point for benchmark-based evaluation. However, the two main ablation claims rely on raw instance counts over a benchmark that contains large families of near-duplicate instances, which weakens the generality of the conclusions as currently stated.

major comments (3)
  1. [Section 6.2, Tables 1-2] The central ablation claim that kernelization followed by branch-and-bound 'significantly outperforms' branch-and-reduce rests on the 26-instance advantage of RMoMC over BnR. Inspection of Tables 1 and 2 shows that 16 of these 26 instances come from one family (n=18096, m=28281, kernel with roughly 580 vertices and 2000 edges, |VC|=11185) and 7 come from a second family (n=15783, m=24663, kernel roughly 510/1750, |VC|=9755). Within each family the rows report identical n, m, kernel size, and optimum, so these are near-duplicates from a common generator rather than independent test cases. Counting them as independent successes overstates the breadth of the evidence; the paper should report per-family success counts and qualify the 'significant' claim accordingly.
  2. [Section 6.2, Tables 1-2] The same duplication problem affects the claimed local-search boost: LSBnR solves 13 more instances than BnR, but 12 of those 13 are from a single family (n=26300, m=41500, kernel 500/3000, |VC|=16300), with instance 181 being the only exception. The evidence that local search 'significantly boosts' branch-and-reduce is thus essentially a result on one graph family. The authors should report how many distinct generator families each configuration solves and use family-level counts, not total instance counts, to support the qualitative conclusion.
  3. [Section 6.1] The paper does not state whether the iterated local search used in LSBnR and FullA is deterministic or how random seeds are chosen. If the ILS is randomized, a single run per instance is not sufficient to separate the reported 13-instance advantage of LSBnR over BnR from seed variation. The authors should either state that their fixed configuration uses a deterministic ILS, or report the variance over multiple seeds (for example, the number of instances solved across 10 independent runs). This is load-bearing for the local-search-boost claim.
minor comments (6)
  1. [Abstract and Section 1] 'Vertex over problem' should be 'vertex cover problem' in the abstract and the introduction.
  2. [Section 4.1] In the desk-reduction description, the condition is printed as '|N(A)\B| ≤ 2, |N(A)\B| ≤ 2, and N(A) ∩ N(B) = ∅'; the second condition should presumably be '|N(B)\A| ≤ 2'.
  3. [Section 4.1] 'An minimum vertex cover' should be 'a minimum vertex cover'.
  4. [Section 6.2] The sentence 'The results are similar to the results on the private instances' should refer to the public instances, since the preceding sentence discusses the private instances.
  5. [Section 7] The conclusion states the solver uses 'all known reduction rules', while Section 4.1 describes the collection as 'extensive (though not exhaustive)'; these statements should be aligned.
  6. [Figure 1] Figure 1 is hard to read at its printed resolution, and the tables do not report per-instance running times, so readers cannot reconstruct the time-to-solution behavior behind the cumulative plot.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper reports external benchmark comparisons of independently defined solver configurations, and the component insights are empirical observations rather than derivations from fitted inputs.

full rationale

This is an experimental systems paper whose central claims are empirical comparisons of fixed algorithm configurations on the external PACE 2019 benchmark. The main comparisons are (1) RMoMC solving 68 public instances versus BnR solving 42, used to argue that kernelization followed by branch-and-bound can outperform branch-and-reduce; (2) LSBnR solving 55 versus BnR solving 42, used to argue that local search priming helps branch-and-reduce; and (3) instances 131 and 157, where MoMC succeeds but RMoMC fails, used to show that kernelization is sometimes counterproductive for branch-and-bound. Each configuration is defined independently in Section 6.2: MoMC runs Li et al.'s MoMC on the complement graph, RMoMC exhaustively reduces and then runs MoMC on the kernel complement, BnR reduces and runs Akiba and Iwata's branch-and-reduce on the kernel, LSBnR additionally seeds branch-and-reduce with an Andrade et al. local-search solution, and FullA combines all phases with disclosed time limits of one second and thirty seconds. No parameter is fitted to the benchmark in order to produce a prediction; the phase time limits and ordering are hand-set and disclosed in Sections 5 and 6.1. The competition result itself was determined by held-out private instances, an external evaluation. The cited components come from prior work by others (Akiba and Iwata [2], Andrade et al. [3], Li et al. [28]); the authors' own prior work (e.g., Strash [36]) is used to motivate the design choice of trying branch-and-bound after kernelization, not as the evidence establishing the paper's stated insights. The 'first time' claim in Section 6.2 is a statement about the prior literature; if it is overbroad, that is a literature-review correctness concern, not circularity. The reviewer's observation that many instances are near-duplicates of a few generated families and that the ILS runs are unrepeated affects how broadly the ablation counts generalize and how strong the statistical support is, but it does not make any claimed result equivalent to its input by construction. No self-referential derivation, fitted-input-as-prediction step, or load-bearing self-citation chain appears in the paper. Therefore the appropriate finding is no significant circularity.

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

The paper contributes an engineering composition of existing algorithms, so the central claims rest on standard equivalences, the correctness of borrowed reduction rules and solvers, and the representativeness of the PACE benchmark. The only hand-set numbers are the phase time limits and the branch-count check; none are fitted to optimize a scalar, but they influence the reported counts and are not sensitivity-tested.

free parameters (3)
  • Short time limit (Phases 2 and 3) = 1 second
    Hand-set in the FullA configuration; not fitted, but affects which instances are solved and is part of the portfolio design.
  • Long time limit (Phase 4) = 30 seconds
    Hand-set; longer branch-and-reduce window before final branch-and-bound; no sensitivity analysis reported.
  • Branch-count limit for MoMC time checking = not stated
    Section 5 footnote says time checking is simulated with a limit on the number of branches; the exact value is omitted.
assumptions (5)
  • standard math The minimum vertex cover of G is the complement of a maximum independent set, which is a maximum clique in the complement graph.
    Used in Sections 1 and 4.3 to justify running MoMC on the complement graph.
  • domain assumption All data reduction rules applied in kernelization preserve the existence of some minimum vertex cover.
    Section 4.1 sketches the rules and cites Akiba and Iwata [2] and Xiao and Nagamochi [43] for correctness; the paper does not prove them.
  • domain assumption Akiba and Iwata's branch-and-reduce implementation and MoMC clique solver solve their respective problems exactly.
    Sections 4.2 and 4.3 adopt these as correct black boxes; correctness of the full solver depends on them.
  • domain assumption The iterated local search of Andrade et al. returns a valid independent set whose complement is a valid vertex cover.
    Section 4.4 uses ILS to seed branch-and-reduce; validity is required for the returned cover to be a true upper bound.
  • domain assumption The PACE 2019 vertex cover instances are representative of typical hard instances for exact vertex cover solvers.
    The empirical claims are drawn from this corpus; the paper notes in Section 3 that reductions rarely work on dense graphs, so generalization to dense instances is not supported.

how reviews work

0 comments
Cite this review

Pith. "Pith review of WeGotYouCovered: The Winning Solver from the PACE 2019 Implementation Challenge, Vertex Cover Track." pith.science (2026). https://pith.science/paper/LSVH3TOH

@misc{pith2026190806795,
  author       = {Pith},
  title        = {Pith review of: WeGotYouCovered: The Winning Solver from the PACE 2019 Implementation Challenge, Vertex Cover Track},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LSVH3TOH}},
  note         = {Machine review of arXiv:1908.06795}
}
read the original abstract

We present the winning solver of the PACE 2019 Implementation Challenge, Vertex Cover Track. The minimum vertex cover problem is one of a handful of problems for which kernelization---the repeated reducing of the input size via data reduction rules---is known to be highly effective in practice. Our algorithm uses a portfolio of techniques, including an aggressive kernelization strategy, local search, branch-and-reduce, and a state-of-the-art branch-and-bound solver. Of particular interest is that several of our techniques were not from the literature on the vertex over problem: they were originally published to solve the (complementary) maximum independent set and maximum clique problems. Aside from illustrating our solver's performance in the PACE 2019 Implementation Challenge, our experiments provide several key insights not yet seen before in the literature. First, kernelization can boost the performance of branch-and-bound clique solvers enough to outperform branch-and-reduce solvers. Second, local search can significantly boost the performance of branch-and-reduce solvers. And finally, somewhat surprisingly, kernelization can sometimes make branch-and-bound algorithms perform worse than running branch-and-bound alone.

Figures

Figures reproduced from arXiv: 1908.06795 by the authors.

Figure 1
Figure 1. Number of instances solved over time by each [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 34 canonical work pages

  1. [1]

    Abu-Khzam, Michael R

    Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, and W. Henry Suters. Crown struc- tures for vertex cover kernelization. Theor. Com- put. Syst. , 41(3):411–430, 2007. doi:10.1007/ s00224-007-1328-0

    work page 2007

  2. [2]

    Akiba and Y

    T. Akiba and Y. Iwata. Branch-and-reduce exponen- tial/FPT algorithms in practice: A case study of vertex cover. Theor. Comput. Sci., 609, Part 1:211–225, 2016. doi:10.1016/j.tcs.2015.09.023

    doi:10.1016/j.tcs.2015.09.023 2016

  3. [3]

    D. V. Andrade, M. G.C. Resende, and R. F. Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18(4):525–547, 2012. doi:10.1007/s10732-012-9196-4

    doi:10.1007/s10732-012-9196-4 2012

  4. [4]

    Batsyn, B

    M. Batsyn, B. Goldengorin, E. Maslov, and P. Parda- los. Improvements to MCS algorithm for the maximum clique problem.J. Comb. Optim., 27(2):397–416, 2014. doi:10.1007/s10878-012-9592-6

    work page doi:10.1007/s10878-012-9592-6 2014

  5. [5]

    Butenko, P

    S. Butenko, P. Pardalos, I. Sergienko, V. Shylo, and P. Stetsyuk. Finding maximum independent sets in graphs arising from coding theory. InProc. 2002 ACM 2https://github.com/wata-orz/vertex_cover 3https://home.mis.u-picardie.fr/~cli/EnglishPage.html Symposium on Applied Computing (SAC’02), pages 542–546. ACM, 2002.doi:10.1145/508791.508897

    arXiv 2002

  6. [6]

    Butenko and S

    S. Butenko and S. Trukhanov. Using critical sets to solve the maximum independent set problem. Oper. Res. Lett., 35(4):519–524, 2007.doi:10.1016/j.orl. 2006.07.004

    doi:10.1016/j.orl 2007

  7. [7]

    Estimating the size of correcting codes using extremal graph prob- lems

    Sergiy Butenko, Panos Pardalos, Ivan Sergienko, Vladimir Shylo, and Petro Stetsyuk. Estimating the size of correcting codes using extremal graph prob- lems. In Charles Pearce and Emma Hunt, editors, Optimization, volume 32 ofSpringer Optimization and Its Applications, pages 227–243. Springer, 2009.doi: 10.1007/978-0-387-98096-6_12

    doi:10.1007/978-0-387-98096-6_12 2009

  8. [8]

    Efficient maximum clique computation over large sparse graphs

    Lijun Chang. Efficient maximum clique computation over large sparse graphs. InProc. 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’19, pages 529–538. ACM, 2019. doi:10.1145/3292500.3330986

    arXiv 2019

Show all 51 references
  1. [9]

    Computing a near-maximum independent set in linear time by reducing-peeling

    Lijun Chang, Wei Li, and Wenjie Zhang. Computing a near-maximum independent set in linear time by reducing-peeling. In Proc. 2017 ACM International Conference on Management of Data (SIGMOD 2017), pages 1181–1196. ACM, 2017.doi:10.1145/3035918. 3035939

    2017 doi

  2. [10]

    Kanj, and Weijia Jia

    Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. Journal of Algorithms, 41(2):280–301, 2001.doi:10. 1006/jagm.2001.1186

    2001

  3. [11]

    Kanj, and Ge Xia

    Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover.Theoretical Computer Science, 411(40):3736–3756, 2010. doi:10.1016/j. tcs.2010.06.026

    2010 doi

  4. [12]

    Tammy M. K. Cheng, Yu-En Lu, Michele Vendruscolo, Pietro Lio’, and Tom L. Blundell. Prediction by graph theoretic measures of structural effects in proteins aris- ing from non-synonymous single nucleotide polymor- phisms. PLOS Computational Biology, 4(7):1–9, 07

  5. [13]

    Lin- ear kernels in linear time, or how to save k colors in o(n2) steps

    Benny Chor, Mike Fellows, and David Juedes. Lin- ear kernels in linear time, or how to save k colors in o(n2) steps. In Juraj Hromkovič, Manfred Nagl, and Bernhard Westfechtel, editors, Graph-Theoretic Con- cepts in Computer Science, pages 257–269. Springer Berlin Heidelberg, ...

    2005 doi

  6. [14]

    JakobDahlum, SebastianLamm, PeterSanders, Chris- tian Schulz, Darren Strash, and Renato F. Werneck. Accelerating local search for the maximum indepen- dent set problem. In Proc. 15th International Sym- posium on Experimental Algorithms (SEA 2016), vol- ume 9685 of LNCS, pages ...

    2016 doi

  7. [15]

    Fellows, Lars Jaffke, Aliz Izabella Király, Frances A

    Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, and Mathias Weller. What Is Known About Vertex Cover Kernelization?, pages 330–356. Springer, 2018. doi:10.1007/ 978-3-319-98355-4_19

    2018

  8. [16]

    A measure & conquer approach for the analy- sis of exact algorithms.Journal of the ACM, 56(5):25,

    Fedor V Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach for the analy- sis of exact algorithms.Journal of the ACM, 56(5):25,

  9. [17]

    Fomin and D

    F.V. Fomin and D. Kratsch. Exact Exponen- tial Algorithms. Springer, 2010. doi:10.1007/ 978-3-642-16533-7

    2010

  10. [18]

    Gardiner, , Peter Willett, and Peter J

    Eleanor J. Gardiner, , Peter Willett, and Peter J. Artymiuk. Graph-theoretic techniques for macro- molecular docking. Journal of Chemical Information and Computer Science, 40(2):273–279, 2000. doi: 10.1021/ci990262o

    doi

  11. [19]

    Gemsa, B

    A. Gemsa, B. Niedermann, and M. Nöllen- burg. Trajectory-Based Dynamic Map La- beling. In Proc. 24th Int. Symp. on Algo- rithms and Computation (ISAAC’13) , LNCS, pages 413–423. Springer, 2013. URL: http: //dx.doi.org/10.1007/978-3-642-45030-3_39

    2013 doi

  12. [20]

    Gottlieb, A

    L. Gottlieb, A. Kontorovich, and R. Krauthgamer. Ef- ficient classification for metric data.IEEE Transac- tions on Information Theory, 60(9):5750–5759, Sep

  13. [21]

    Harary and I

    F. Harary and I. C. Ross. A Procedure for Clique De- tection Using the Group Matrix.Sociometry, 20(3):pp. 205–215, 1957. URL:http://www.jstor.org/stable/ 2785673

    1957

  14. [22]

    Hespe, C

    D. Hespe, C. Schulz, and D. Strash. Scalable kernel- ization for maximum independent sets. InProceedings of the Twentieth Workshop on Algorithm Engineer- ing and Experiments, ALENEX 2018, New Orleans, LA, USA, January 7-8, 2018., pages 223–237, 2018. doi:10.1137/1.9781611975055.19

    2018 doi

  15. [23]

    WeGotYouCovered, May 2019

    Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. WeGotYouCovered, May 2019. doi:10.5281/zenodo.2816116

    2019 doi

  16. [24]

    Iwata, K

    Y. Iwata, K. Oka, and Y. Yoshida. Linear-time FPT Algorithms via Network Flow. In Proc. 25th ACM- SIAM Symposium on Discrete Algorithms, SODA ’14, pages 1749–1761. SIAM, 2014. URL:http://dl.acm. org/citation.cfm?id=2634074.2634201

    2014

  17. [25]

    A Fine-grained Analysis of a Simple Indepen- dent Set Algorithm

    Joachim Kneis, Alexander Langer, and Peter Ross- manith. A Fine-grained Analysis of a Simple Indepen- dent Set Algorithm. In Ravi Kannan and K. Narayan Kumar, editors, Proc. 29th International Conference on Foundations of Software Technology and Theoret- ical Computer Science ...

    2009

  18. [26]

    C.E. Larson. A note on critical independence reduc- tions. volume 51 ofBulletin of the Institute of Combi- natorics and its Applications, pages 34–46, 2007

    2007

  19. [27]

    C. Li, Z. Fang, and K. Xu. Combining MaxSAT Rea- soning and Incremental Upper Bound for the Maxi- mum Clique Problem. InProceedings of 25th Interna- tional Conference on Tools with Artificial Intelligence (ICTAI), pages 939–946, Nov 2013. doi:10.1109/ ICTAI.2013.143

    2013

  20. [28]

    C.-M. Li, H. Jiang, and F. Manyà. On minimiza- tion of the number of branches in branch-and-bound algorithms for the maximum clique problem. Com- puters & Operations Research, 84:1–15, 2017. doi: 10.1016/j.cor.2017.02.017

    2017 doi

  21. [29]

    An efficient branch- and-bound algorithm based on MaxSAT for the max- imum clique problem

    Chu Min Li and Zhe Quan. An efficient branch- and-bound algorithm based on MaxSAT for the max- imum clique problem. In Proceedings of the Twenty- Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010,

    2010

  22. [30]

    Nemhauser and L

    G.L. Nemhauser and L. E. Trotter Jr. Vertex pack- ings: Structural properties and algorithms.Mathemat- ical Programming, 8(1):232–248, 1975.doi:10.1007/ BF01580444

    1975

  23. [31]

    Peaty: an exact solver for the vertex cover problem, May 2019.doi: 10.5281/zenodo.3082356

    Patrick Prosser and James Trimble. Peaty: an exact solver for the vertex cover problem, May 2019.doi: 10.5281/zenodo.3082356

    2019 doi

  24. [32]

    San Segundo, F

    P. San Segundo, F. Matia, D. Rodriguez-Losada, and M. Hernando. An improved bit parallel exact max- imum clique algorithm. Optim. Lett., 7(3):467–479,

  25. [33]

    P.SanSegundo, D.Rodríguez-Losada, andA. Jiménez. Anexactbit-parallelalgorithmforthemaximumclique problem. Comput. Oper. Res., 38(2):571–581, 2011. doi:10.1016/j.cor.2010.07.019

    2011 doi

  26. [34]

    Pardalos

    Pablo San Segundo, Alvaro Lopez, and Panos M. Pardalos. A new exact maximum clique algorithm for large and massive sparse graphs. Computers & Operations Research, 66:81–94, 2016. doi:10.1016/ j.cor.2015.07.013

    2016

  27. [35]

    Sander, Diego Nehab, Eden Chlamtac, and Hugues Hoppe

    Pedro V. Sander, Diego Nehab, Eden Chlamtac, and Hugues Hoppe. Efficient traversal of mesh edges using adjacency primitives. ACM Trans. Graph., 27(5):144:1–144:9, December 2008. doi:10.1145/ 1409060.1409097

    2008

  28. [36]

    On the power of simple reduc- tions for the maximum independent set problem

    Darren Strash. On the power of simple reduc- tions for the maximum independent set problem. In Proc. 22nd International Computing and Combina- torics Conference (COCOON 2016), volume 9797 of LNCS, pages 345–356. Springer, 2016.doi:10.1007/ 978-3-319-42634-1_28

    2016

  29. [37]

    Szabó and B

    S. Szabó and B. Zaválnij. A different approach to max- imum clique search. In2018 20th International Sym- posium on Symbolic and Numeric Algorithms for Sci- entific Computing (SYNASC), pages 310–316. IEEE, Sep. 2018. doi:10.1109/SYNASC.2018.00055

    2018

  30. [38]

    R. E. Tarjan and A. E. Trojanowski. Finding a max- imum independent set. SIAM J. Comput., 6(3):537– 546, 1977. doi:10.1137/0206038

    1977 doi

  31. [39]

    Tomita, Y

    E. Tomita, Y. Sutani, T. Higashi, S. Takahashi, and M. Wakatsuki. A simple and faster branch-and-bound algorithm for finding a maximum clique. In Md. Saidur Rahman and Satoshi Fujita, editors, Algorithms and Computation (WALCOM’10), volume 5942 ofLNCS, pages 191–203. Springer B...

    2010 doi

  32. [40]

    Solving the maximum clique and vertex coloring prob- lems on very large sparse networks.INFORMS Jour- nal on Computing, 27(1):164–177, 2015.doi:10.1287/ ijoc.2014.0618

    Anurag Verma, Austin Buchanan, and Sergiy Butenko. Solving the maximum clique and vertex coloring prob- lems on very large sparse networks.INFORMS Jour- nal on Computing, 27(1):164–177, 2015.doi:10.1287/ ijoc.2014.0618

    2015

  33. [41]

    Wu and J

    Q. Wu and J. Hao. A review on algorithms for max- imum clique problems. European Journal of Opera- tional Research, 242(3):693 – 709, 2015.doi:10.1016/ j.ejor.2014.09.064

    2015

  34. [42]

    Xiang, C

    J. Xiang, C. Guo, and A. Aboulnaga. Scalable maxi- mum clique computation using mapreduce. In Proc. IEEE 29th International Conference on Data Engi- neering (ICDE’13), pages 74–85, April 2013. doi: 10.1109/ICDE.2013.6544815

    2013

  35. [43]

    Xiao and H

    M. Xiao and H. Nagamochi. Confining sets and avoid- ing bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs.Theor. Comput. Sci., 469:92–104, 2013.doi:10.1016/j.tcs.2012.09.022

    2013 doi

  36. [44]

    Exact algo- rithms for maximum independent set.Information and Computation, 255:126–146, 2017.doi:10.1016/j.ic

    Mingyu Xiao and Hiroshi Nagamochi. Exact algo- rithms for maximum independent set.Information and Computation, 255:126–146, 2017.doi:10.1016/j.ic. 2017.06.001

    2017 doi

  37. [45]

    M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New Algorithms for Fast Discovery of Association Rules. In 3rd International Conference on Knowledge Discovery and Data Mining, pages 283–286. AAAI Press, 1997

    1997

  38. [46]

    zbogdan/pace-2019 a, May 2019

    Bogdan Zavalnij. zbogdan/pace-2019 a, May 2019. doi:10.5281/zenodo.3228802. Table 1: Detailed per instance results for public instances. The columnsn and m refer to the number of nodes and edges of the input graph,n′ and m′ refer to the number of nodes and edges of the kernel ...

    2019 doi

  39. [2008]

    doi:10.1371/journal.pcbi.1000135

    doi

  40. [2009]

    doi:10.1145/1552285.1552286

  41. [2010]

    URL: http://www.aaai.org/ocs/index.php/ AAAI/AAAI10/paper/view/1611

  42. [2013]

    doi:10.1007/s11590-011-0431-y

    doi

  43. [2014]

    doi:10.1109/TIT.2014.2339840

    2014

Pith tools

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