Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem

T0 review · 4 major / 5 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 claims that optimal branching rules for maximum independent set can be generated automatically for each subgraph, on the fly, and that the resulting exact algorithms branch less than those using expert-designed rules.

desk verdict Novel set-cover reduction for automated branching rules, with a real but fixable gap in the claimed optimality proof. read the letter →

arxiv 2412.07685 v1 pith:UV4AXA4F submitted 2024-12-10 math.OC cs.DSmath.CO

Xuan-Zhao Gao , Yi-Jia Wang , Pan Zhang , Jin-Guo Liu This is my paper · ORCID
classification math.OCcs.DSmath.CO MSC 90C2705C6968V15
keywords maximumindependentsetbranchingalgorithmweightedminimumcoveringcomplexityon-the-flybranch-and-reduce3-regulargraphsreducedalpha-tensorexactexponential-time
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

This paper claims that the branching rules used by exact exponential-time algorithms for the maximum independent set problem can be discovered automatically instead of designed by hand. For any subgraph with a few dozen vertices, choosing the rule with the smallest branching factor is reformulated as a weighted minimum set covering problem and solved with standard optimization tools. Because the rule is generated on the fly for the subgraph currently being processed, it adapts to local structure, and the paper reports that it produces fewer branches than established expert-designed rules. On 3-regular graphs the average fitted complexity is $O(1.0441^n)$, below the previous best average values.

What carries the argument

The engine is the reduction of branching-rule search to weighted minimum set covering. A reduced $\alpha$-tensor prunes irrelevant boundary configurations; the surviving configurations, grouped by boundary assignment, form the universe $S_R$ that a branching rule must cover. Each candidate clause $c_i$ is assigned to the set $J_i$ of configurations it satisfies and carries weight $\gamma^{-\Delta\rho(c_i)}$, where $\Delta\rho(c_i)$ is the reduction in the complexity measure when the clause fixes its literals. Finding the rule of smallest $\gamma$ is then the weighted set cover problem of equations (3.2)–(3.4), solved by integer programming or its LP relaxation inside Algorithm 3.2's fixed-point iteration; the paper's candidate-clause generator restricts to intersections of singleton clauses to keep the cover small.

What would settle it

Enumerate all valid DNF branching rules for a small subgraph—for example the 8-vertex PH2 instance of Section 4.2—without the intersection-only restriction, compute the true minimum $\gamma$ over every clause, and compare it with the value from Algorithm 3.1. If any excluded clause participates in a cover with a strictly smaller $\gamma$, the claimed optimality is false; the PH2 table has only five relevant configurations, so such an exhaustive check is computationally feasible.

Watch

Extended reading notes

Core claim

The paper's central claim is that, for a subgraph $R$, the optimal branching rule—the valid DNF rule with the smallest branching complexity $\gamma$—can be obtained from the reduced $\alpha$-tensor of $R$. The relevant local configurations are grouped by boundary assignment into boundary-grouped MISs $S_R$, each candidate clause is represented by the set of configurations it covers with cost $\gamma^{-\Delta\rho(c_i)}$, and the search over rules becomes a weighted minimum set covering problem. The paper solves this cover iteratively, updating $\gamma$ until the cover's total cost equals $1$, and reports that the resulting rules improve on human-derived rules: the PH2 subgraph rule has branching vector $\{16,16,16\}$ with $\gamma\approx1.0711$ versus $1.0718$, and on 3-regular graphs the on-the-fly algorithm reaches average complexity $O(1.0441^n)$.

Load-bearing premise

The load-bearing premise sits in Section 3.2, right after Algorithm 3.1: the algorithm throws away every clause that is not an intersection of single-configuration clauses, and the paper asserts without proof that this does not sacrifice optimality. If an optimal rule needs one of those discarded clauses, the reported $\gamma$ values are not true minima.

Editorial extensions

If this is right

  • On 3-regular graphs, the on-the-fly algorithm with Xiao's reductions attains an average branching factor of $1.0441$, below xiao2013's $1.0487$ and far below the theoretical $O(1.0836^n)$ bound of the earlier algorithm.
  • The PH2 bottleneck case, previously handled by a two-branch manual rule with $\gamma=1.0718$, is improved by an automatically generated three-branch rule with $\gamma=1.0711$, so at least one expert bottleneck is not optimal.
  • Known structural rules, such as the domination rule, reappear as solutions of the set-cover problem, indicating that hand-designed rules can be recovered as instances of the same principle.
  • Using the LP relaxation instead of integer programming increases the number of branches only slightly, so on-the-fly generation remains practical on larger graphs.
  • On Erdős–Rényi, King's subgraph, and grid graphs, the same on-the-fly method with d1/d2 plus Xiao reductions gives performance comparable to a benchmark branch-and-reduce solver that uses an extra packing rule.

Reading between the lines

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

  • Because the reduction only needs a finite table of boundary-grouped configurations, the same pipeline should transfer to vertex cover, Max-SAT, and other constraint satisfaction problems with a local complexity measure; the paper lists these as future work but does not test them.
  • The optimality of the generated rule is exactly as strong as the unproved clause-filtering step, so an independent brute-force check over all clauses for small subgraphs would either certify or bound the 'provably optimal' claim; the paper's PH2 example is small enough for such a check.
  • A natural next step is to turn the average-case $O(1.0441^n)$ 3-regular result into a worst-case statement by running the fixed-point search on a carefully chosen finite set of subgraphs and composing the resulting rules; the paper's current evidence for $1.0441$ is numerical fitting, not a proof.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes an automated framework for generating branching rules for exact maximum independent set algorithms. For a chosen subgraph R, the method first computes boundary-grouped maximum independent sets via a reduced α-tensor, then constructs a candidate set of DNF clauses, and finally searches for a minimum-complexity valid branching rule by solving a weighted minimum set covering problem with integer programming or its LP relaxation. The authors report rediscovering known rules, finding a slightly better rule for a PH2 bottleneck subgraph, and implementing an on-the-fly branch-and-reduce solver whose fitted average branching factors on 3-regular and other graphs improve on several existing methods. Appendices provide pruning details, a fixed-point convergence argument, worst-case data, and a software guide.

Significance. If the optimality and completeness claims are fully established, this is a valuable contribution: it replaces hand-designed branching rules with rules generated for each local subgraph, connects branching-rule search to set covering and integer programming, and provides an open-source Julia implementation. The numerical experiments are suggestive and the code release is a concrete strength. However, the central optimality claim currently rests on an unproved and internally inconsistent candidate-clause filtering step, and the α-tensor pruning argument is only sketched, so the 'provably optimal' assertion in the abstract is not yet backed by a complete proof.

major comments (4)
  1. [Section 3.2, Algorithm 3.1] The claim following Algorithm 3.1 that restricting clauses to intersections of singleton covers 'does not sacrifice the optimality of the branching rule' is load-bearing and unproved. The text says that only the clause with the longest length is kept for a given covered set, but the pseudocode adds every nonempty intersection without any length comparison, and Table 2 even lists singletons such as ¬a and ¬e. If the implementation prunes more aggressively than the pseudocode, the computed γ can overestimate the true optimum; if it follows the pseudocode, the completeness of C with respect to all possible DNF rules is still asserted without proof. Since Eq. (3.2) is the basis for the optimality claims in Sections 4 and 5, this needs to be settled by a theorem or a counterexample.
  2. [Appendix A, Definitions A.1-A.2 and Eq. (A.3)] The reduction from the α-tensor to the reduced α-tensor is not fully justified. Definition A.2 declares a boundary configuration t irrelevant when s ≺ t and α(R)_s ≥ α(R)_t, but the statement that any completion of t to G\R can be matched or improved by s is asserted rather than proved for arbitrary environments. The same applies to the enhanced pruning criterion in Eq. (A.3). An unsound pruning step would remove configurations needed for an optimal branching rule and would invalidate the 'provably optimal' claim, so a rigorous dominance proof is required.
  3. [Appendix B, Theorems B.1-B.2] The fixed-point convergence proof covers only starting points γ > γ0. Theorem B.2 asserts that the sequence is bounded below by γ0, but this is not shown in the written proof; it also does not discuss the behavior of the iteration when the initial value γ = 2 is not strictly greater than γ0 or when the WMSC solver returns only an approximate solution. Since Algorithm 3.2 is the practical engine for obtaining exact optimal rules, these points should be made precise, including a clear statement that the LP-relaxation variant used in Section 5.3 is not covered by the optimality guarantee.
  4. [Section 5.2, Table 8] The reported average branching factors are the empirical basis for the abstract's claim of O(1.0441^n) 'better than any previous methods,' but the fitting procedure, the number of samples per point, the size ranges, and the variability of the fitted exponents are not reported. Without error bars or a description of the fitting method, it is difficult to judge whether the differences between 1.0441 and 1.0487 are statistically significant. Please add fitting details, confidence intervals, and the underlying data or a link to it.
minor comments (5)
  1. [Section 3.2, Eq. (3.2)] The optimization problem in Eq. (3.2) does not explicitly state that x_i ∈ {0,1}; the integrality constraint first appears in Eq. (3.7). Please state it at the point of definition.
  2. [Section 5.1 and Table 7] The statement that the packing rule can be automatically discovered by the optimal branching algorithm seems to conflict with the earlier statement that reduction rules requiring more sophisticated rewriting do not fit the branching framework. Please clarify which reduction rules are actually reproduced by the optimal branching method.
  3. [Definition 2.2, Eq. (2.1)] The branching complexity equation is presented without discussing overlapping clauses; if clauses overlap, the equation gives an upper bound rather than an exact recurrence, and this distinction should be noted explicitly.
  4. [Theorem 3.7] The O(log(ϵ^{-1})) time claim assumes an oracle for the NP-hard WMSC problem; this assumption should be stated explicitly in the theorem statement.
  5. [Throughout] There are several typographical issues, including 'Erdos-Renyi' for 'Erdős–Rényi', 'the algorithmsob' for 'the algorithms ob', and missing spaces in 'thatintegerprogrammingprogress' in Appendix B. A careful proofreading pass is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the optimal-branching construction is a genuine set-cover optimization, and the reported complexity figures are empirical fits to measured branch counts rather than assumed inputs.

full rationale

The derivation chain is self-contained. Section 3.2 converts valid branching-rule search into a weighted minimum set covering problem (Eqs. 3.2-3.4); the objective and constraints follow from Definition 2.2 and Definition 3.5, not from the answer being sought. The reported gamma values (Table 8) are explicitly fitted from branch-count data in Figure 5, so they are outputs of the numerical experiment, not parameters whose fitted values are relabeled as predictions. The candidate-clause filter in Algorithm 3.1 is asserted to preserve optimality without proof; this is a completeness gap, not circularity, because the optimality criterion is defined independently of the filter. Section 4.3 likewise states that a rigorous proof of lower complexity for its tree-like environment is left as future work; that is a limitation on the strength of the example, not a circular step. The alpha-tensor definition cites the authors' prior papers [34,35], but the present paper restates the definitions and supplies its own reduction arguments in Appendix A; those self-citations are not load-bearing in the sense of making the conclusion equivalent to a citation. Comparisons to xiao2013 and akiba2015 are external, and no uniqueness theorem from the authors is invoked to force the chosen rule. No step reduces Eq. (3.2) to the data it is supposed to explain.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

The method introduces no fitted constants; the primary user choices are the complexity measure rho and the heuristic subgraph selection, which are treated as modeling axioms. The formalisms of reduced alpha-tensor and boundary-grouped MISs are new abstractions without external falsifiable handles, and several optimality claims rest on unproven statements about candidate clause completeness and pruning safety.

assumptions (6)
  • domain assumption Branching strategies for MIS can be represented without loss of generality as DNF formulas over the subgraph's vertices (Definition 2.1).
    The paper restricts branching to a single-level DNF rule on the selected subgraph. If an optimal strategy requires a multi-step or non-DNF structure, the optimality claim does not cover it.
  • standard math The branching complexity gamma defined by Equation (2.1) correctly measures the recursion tree size for the chosen measure rho.
    This is the standard measure-and-conquer recurrence for branching algorithms; the paper relies on it without proof.
  • domain assumption The reduced alpha-tensor and boundary-grouped MISs capture all local configurations needed to find a global MIS (Appendix A).
    The pruning of 'irrelevant' boundary configurations uses a partial-order argument that assumes the environment G\R does not invalidate the dominance relation. The enhanced pruning in A.2 adds nearest-neighbor assumptions.
  • ad hoc to paper Algorithm 3.1's candidate clause set contains at least one optimal branching rule.
    The paper states that discarding non-intersection clauses 'does not sacrifice the optimality' but provides no formal proof. This is the weakest link in the optimality chain.
  • domain assumption For the PH2 and bottleneck-case demonstrations, the environment N3[R] is tree-like with specific degree conditions (Section 4.2, 4.3).
    These assumptions are used to compute Delta-rho values and to claim a better gamma than manual rules; the paper admits a rigorous proof of the lower complexity is future work.
  • domain assumption The WMSC solver (SCIP) returns exact solutions for the integer program in practical time.
    The empirical efficiency of the on-the-fly method depends on SCIP solving NP-hard set cover instances with thousands of sets in milliseconds, which is asserted but not formally bounded.
invented entities (2)
  • reduced alpha-tensor
    purpose: Prune irrelevant boundary configurations to define the boundary-grouped MISs needed for the set cover instance.
    A mathematical abstraction introduced in this paper; its safety is justified by an internal partial-order argument, not by an external falsifiable prediction.
  • boundary-grouped MISs
    purpose: Group local MIS configurations by boundary configuration so that the branching rule can be expressed as a set cover over these groups.
    An internal formalism that defines the elements of the set cover problem; it has no independent falsifiable handle outside the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem." pith.science (2026). https://pith.science/paper/UV4AXA4F

@misc{pith2026241207685,
  author       = {Pith},
  title        = {Pith review of: Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UV4AXA4F}},
  note         = {Machine review of arXiv:2412.07685}
}
read the original abstract

The branching algorithm is a fundamental technique for designing fast exponential-time algorithms to solve combinatorial optimization problems exactly. It divides the entire solution space into independent search branches using predetermined branching rules, and ignores the search on suboptimal branches to reduce the time complexity. The complexity of a branching algorithm is primarily determined by the branching rules it employs, which are often designed by human experts. In this paper, we show how to automate this process with a focus on the maximum independent set problem. The main contribution is an algorithm that efficiently generate optimal branching rules for a given sub-graph with tens of vertices. Its efficiency enables us to generate the branching rules on-the-fly, which is provably optimal and significantly reduces the number of branches compared to existing methods that rely on expert-designed branching rules. Numerical experiment on 3-regular graphs shows an average complexity of O(1.0441^n) can be achieved, better than any previous methods.

Figures

Figures reproduced from arXiv: 2412.07685 by the authors.

Figure 1
Figure 1. Applying a MIS branching strategy on a sub-graph [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. An example subgraph, where the j, k, l are the boundary vertices. It satisfies the condition of domination rule, where N[v] ⊆ N[w]. sjkl α˜ (R)s∂R swvjkl 000 1 01000, 10000 010 2 01010 101 2 00101 111 3 00111 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. The example of PH2 (composed of a pentagon and a hexagon sharing 2 edges) with a tree-like neighborhood. The vertices connected by dashed lines indicate their connections to vertices in the further environment. i Ji ci ∆ρ(ci) 1 {1} ¬a ∧ ¬b ∧ c ∧ ¬d ∧ e ∧ f ∧ ¬g ∧ ¬h 18 2 {2} ¬a ∧ b ∧ ¬c ∧ ¬d ∧ e ∧ ¬f ∧ g ∧ ¬h 16 3 {3} ¬a ∧ b ∧ ¬c ∧ d ∧ ¬e ∧ ¬f ∧ ¬g ∧ h 18 4 {4} a ∧ ¬b ∧ c ∧ ¬d ∧ ¬e ∧ f ∧ ¬g ∧ h 22 5 {5} a ∧ ¬b ∧ ¬c … view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: The example of the bottleneck case in Ref. [ [PITH_FULL_IMAGE:figures/full_fig_p014_4.png]
Figure 5
Figure 5. Figure 5: The average number of branches produced by various algorithms on different [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]
Figure 6
Figure 6. Figure 6: The average number of branches produced by [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: An example of the fixed point iteration of [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]
Figure 8
Figure 8. Figure 8: The largest number of branches produced by various algorithms on different [PITH_FULL_IMAGE:figures/full_fig_p025_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Programming guide for solving constraint satisfaction problems with tensor networks

    physics.comp-ph 2024-12 conditional novelty 3.0 of 10

    This guide demonstrates how to use the Julia packages GenericTensorNetworks.jl, OMEinsum.jl, and ProblemReductions.jl to represent constraint satisfaction problems as tensor networks, optimize contraction orders, and ...

Reference graph

Works this paper leans on

48 extracted references · 26 canonical work pages · cited by 1 Pith paper

  1. [35]

    J.-G. Liu, J. Wurtz, M.-T. Nguyen, M. D. Lukin, H. Pichler, and S.-T. W ang , Computer-assisted gadget design and problem reduction of unweighted maximum indepen- dent set, unpublished, (2024)

    work page 2024

  2. [1]

    Abrame and D

    A. Abrame and D. Habet , Ahmaxsat: Description and evaluation of a branch and bound Max-SAT solver, J. Satisf. Boolean Model. Comput., 9 (2015), pp. 89–128, https://doi. org/10.3233/SAT190104

    work page doi:10.3233/sat190104 2015

  3. [2]

    Achterberg , SCIP: Solving constraint integer programs, Math

    T. Achterberg , SCIP: Solving constraint integer programs, Math. Program. Comput., 1 (2009), pp. 1–41, https://doi.org/10.1007/s12532-008-0001-1

    doi:10.1007/s12532-008-0001-1 2009

  4. [3]

    Achterberg, T

    T. Achterberg, T. Berthold, T. Koch, and K. Wolter , Constraint integer program- ming: A new approach to integrate CP and MIP, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Springer Berlin Heidelberg, 2008, pp. 6–20, https://doi.org/10.1007/978-3-540-68155-7_4

    work page doi:10.1007/978-3-540-68155-7_4 2008

  5. [4]

    Achterberg, T

    T. Achterberg, T. Koch, and A. Martin , Branching rules revisited, Oper. Res. Lett., 33 (2005), pp. 42–54, https://doi.org/10.1016/j.orl.2004.04.002

    doi:10.1016/j.orl.2004.04.002 2005

  6. [5]

    Akiba and Y

    T. Akiba and Y. Iw ata, Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover, Theoretical Computer Science, 609 (2016), pp. 211–225, https://doi. org/10.1016/j.tcs.2015.09.023

    doi:10.1016/j.tcs.2015.09.023 2016

  7. [6]

    M. Alekhnovich , Lower bounds for k-DNF resolution on random 3-CNFs, in Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2005, p. 251–256, https://doi.org/10.1145/1060590.1060628

    arXiv 2005

  8. [7]

    Argelich, C

    J. Argelich, C. M. Li, F. Manyà, and J. R. Soler , Clause branching in MaxSAT and MinSAT, in Artificial Intelligence Research and Development, IOS Press, 2018, pp. 17–26, https://doi.org/10.3233/978-1-61499-918-8-17

    work page doi:10.3233/978-1-61499-918-8-17 2018

Show all 48 references
  1. [8]

    Bezanson, A

    J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah , Julia: A fresh approach to numerical computing, SIAM Rev., 59 (2017), pp. 65–98

    2017

  2. [9]

    Bourgeois, B

    N. Bourgeois, B. Escoffier, V. T. Paschos, and J. M. v an Rooij , Fast algorithms for max independent set, Algorithmica, 62 (2012), pp. 382–415, https://doi.org/10.1007/ s00453-010-9460-7

    2012

  3. [10]

    Carpaneto and P

    G. Carpaneto and P. Toth , Some new branching and bounding criteria for the asymmetric travelling salesman problem, Manage. Sci., 26 (1980), pp. 736–743, https://doi.org/10. 1287/mnsc.26.7.736

    1980

  4. [11]

    Chen and I

    J. Chen and I. A. Kanj , Improved exact algorithms for Max-SAT, Discrete Appl. Math., 142 (2004), pp. 17–27, https://doi.org/10.1016/j.dam.2003.03.002

    2004 doi

  5. [12]

    M. B. Cohen, Y. T. Lee, and Z. Song , Solving linear programs in the current matrix multiplication time, J. ACM, 68 (2021), pp. 1–39, https://doi.org/10.1145/3424305

    2021 doi

  6. [13]

    Cygan, F

    M. Cygan, F. V. Fomin, Ł. Kow alik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh , Lower bounds based on the exponential-time hy- pothesis, Springer International Publishing, 2015, pp. 467–521, https://doi.org/10.1007/ 978-3-319-21275-3_14

    2015

  7. [14]

    Dunning, J

    I. Dunning, J. Huchette, and M. Lubin , JuMP: A modeling language for mathematical optimization, SIAM Rev., 59 (2017), pp. 295–320, https://doi.org/10.1137/15M1020575

    2017 doi

  8. [15]

    Ebadi, A

    S. Ebadi, A. Keesling, M. Cain, T. T. W ang, H. Levine, D. Bluvstein, G. Semegh- ini, A. Omran, J.-G. Liu, R. Samajdar, et al. , Quantum optimization of maximum independent set using rydberg atom arrays, Science, 376 (2022), pp. 1209–1215

    2022

  9. [16]

    Eppstein , The traveling salesman problem for cubic graphs, J

    D. Eppstein , The traveling salesman problem for cubic graphs, J. Graph Algorithms Appl., 11 (2003), pp. 307–318, https://doi.org/10.1007/978-3-540-45078-8_27

    2003 doi

  10. [17]

    F airbanks, M

    J. F airbanks, M. Besançon, S. Simon, J. Hoffiman, N. Eubank, and S. Karpinski , Juliagraphs/graphs.jl: an optimized graphs package for the julia programming language, 2021, https://github.com/JuliaGraphs/Graphs.jl/

    2021

  11. [18]

    Fischetti and M

    M. Fischetti and M. Monaci , Backdoor branching, in Integer Programming and Combinatoral Optimization, Springer, 2011, pp. 183–191, https://doi.org/10.1007/ 978-3-642-20807-2_15

    2011

  12. [19]

    F. V. Fomin, F. Grandoni, and D. Kratsch , Measure and conquer: A simpleO(20.288n) independent set algorithm, in Proceedings of the Seventeenth Annual ACM-SIAM Sym- posium on Discrete Algorithm, Society for Industrial and Applied Mathematics, 2006, p. 18–25, https://doi.org/10...

    2006

  13. [20]

    F. V. Fomin and K. Høie , Pathwidth of cubic graphs and exact algorithms, Inf. Process. Lett., 97 (2006), pp. 191–196, https://doi.org/10.1016/j.ipl.2005.10.012. 20

    2006 doi

  14. [21]

    F. V. Fomin and P. Kaski , Exact exponential algorithms, Commun. ACM, 56 (2013), pp. 80– 88, https://doi.org/10.1145/2428556.2428575

    2013

  15. [22]

    Gamrath and C

    G. Gamrath and C. Schubert , Measuring the impact of branching rules for mixed-integer programming, in Operations Research Proceedings 2017, Springer International Publishing, 2018, pp. 165–170, https://doi.org/10.1007/978-3-319-89920-6_23

    2017 doi

  16. [23]

    X. Gao, Y. W ang, and J.-G. Liu , OptimalBranching.jl: An implementation of the opti- mal branching algorithm in Julia. https://github.com/ArrogantGao/OptimalBranching.jl, 2024

    2024

  17. [24]

    Hespe, S

    D. Hespe, S. Lamm, C. Schulz, and D. Strash , Wegotyoucovered: The winning solver from the pace 2019 challenge, vertex cover track, in 2020 proceedings of the SIAM workshop on combinatorial scientific computing, SIAM, 2020, pp. 1–11, https://epubs.siam.org/doi/ abs/10.1137/1.9...

    2019 doi

  18. [25]

    Huangfu and J

    Q. Huangfu and J. J. Hall , Parallelizing the dual revised simplex method, Math. Program. Comput., 10 (2018), pp. 119–142, https://doi.org/10.1007/s12532-017-0130-5

    2018 doi

  19. [26]

    Impagliazzo and R

    R. Impagliazzo and R. Paturi, On the complexity of k-SAT, J. Comput. Syst. Sci., 62 (2001), pp. 367–375, https://doi.org/10.1006/jcss.2000.1727

    2001

  20. [27]

    Issac and R

    D. Issac and R. Jaisw al , An O∗(1.0821n)-time algorithm for computing maximum indepen- dent set in graphs with bounded degree 3, 2022, https://doi.org/10.48550/arXiv.1308.1351

    2022 doi arXiv

  21. [28]

    Jian, An O(20.304n) algorithm for solving maximum independent set problem, IEEE Trans

    T. Jian, An O(20.304n) algorithm for solving maximum independent set problem, IEEE Trans. Comput., 35 (1986), p. 847–851, https://doi.org/10.1109/TC.1986.1676847

    1986

  22. [29]

    Khalil, P

    E. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina , Learning to branch in mixed integer programming, AAAI Conf. Artif. Intell., 30 (2016), https://doi.org/10.1609/ aaai.v30i1.10080

    2016

  23. [30]

    Kneis, A

    J. Kneis, A. Langer, and P. Rossmanith , A fine-grained analysis of a simple independent set algorithm, in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2009, pp. 287–2...

    2009

  24. [31]

    A. H. Land and A. G. Doig ,An automatic method of solving discrete programming problems, Econometrica, 28 (1960), pp. 497–520, https://doi.org/10.2307/1910129

    1960 doi

  25. [32]

    Le Bodic and G

    P. Le Bodic and G. Nemhauser , An abstract model for branching and its application to mixed integer programming, Math. Program., 166 (2017), pp. 369–405, https://doi.org/10. 1007/s10107-016-1101-8

    2017

  26. [33]

    C. M. Li, F. Manyà, and J. Planes , Exploiting unit propagation to compute lower bounds in branch and bound Max-SAT solvers, in Principles and Practice of Constraint Program- ming - CP 2005, Springer Berlin Heidelberg, 2005, pp. 403–414, https://doi.org/10.1007/ 11564751_31

    2005

  27. [34]

    J.-G. Liu, X. Gao, M. Cain, M. D. Lukin, and S.-T. W ang , Computing solution space properties of combinatorial optimization problems via generic tensor networks, SIAM J. Sci. Comput., 45 (2023), pp. A1239–A1270, https://doi.org/10.1137/22M1501787

    2023 doi

  28. [36]

    Lubin, O

    M. Lubin, O. Dowson, J. Dias Garcia, J. Huchette, B. Legat, and J. P. Vielma, JuMP 1.0: Recent improvements to a modeling language for mathematical op- timization, Math. Program. Comput., 15 (2023), p. 581–589, https://doi.org/10.1007/ s12532-023-00239-3

    2023

  29. [37]

    I. L. Markov and Y. Shi , Simulating quantum computation by contracting tensor networks, SIAM J. Comput., 38 (2008), pp. 963–981, https://doi.org/10.1137/050644756

    2008 doi

  30. [38]

    Moore and S

    C. Moore and S. Mertens , The nature of computation, Oxford University Press, 2011, https://doi.org/10.1093/acprof:oso/9780199233212.001.0001

    2011

  31. [39]

    D. R. Morrison, S. H. Jacobson, J. J. Sauppe, and E. C. Sewell , Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning, Discrete Optim., 19 (2016), pp. 79–102, https://doi.org/10.1016/j.disopt.2016.01.005

    2016 doi

  32. [40]

    Nabli, An overview on the simplex algorithm, Appl

    H. Nabli, An overview on the simplex algorithm, Appl. Math. Comput., 210 (2009), pp. 479– 489, https://doi.org/10.1016/j.amc.2009.01.013

    2009 doi

  33. [41]

    Peres and M

    F. Peres and M. Castelli , Combinatorial optimization problems and metaheuristics: Re- view, challenges, design, and development, Appl. Sci., 11 (2021), p. 6449, https://doi.org/ 10.3390/app11146449

    2021 doi

  34. [42]

    Robson, Algorithms for maximum independent sets, J

    J. Robson, Algorithms for maximum independent sets, J. Algorithms, 7 (1986), pp. 425–440, https://doi.org/10.1016/0196-6774(86)90032-5

    1986 doi

  35. [43]

    R. E. Tarjan and A. E. Trojanowski , Finding a maximum independent set, SIAM J. Comput., 6 (1977), pp. 537–546, https://doi.org/10.1137/0206038. 21

    1977 doi

  36. [44]

    Urquhart, The complexity of propositional proofs, Bull

    A. Urquhart, The complexity of propositional proofs, Bull. Symb. Log., 1 (1995), pp. 425–467, https://doi.org/10.2307/421131

    1995 doi

  37. [45]

    Xiao, New branching rules: Improvements on independent set and vertex cover in sparse graphs, arXiv:0904.2712, (2009), https://doi.org/10.48550/arXiv.0904.2712

    M. Xiao, New branching rules: Improvements on independent set and vertex cover in sparse graphs, arXiv:0904.2712, (2009), https://doi.org/10.48550/arXiv.0904.2712

    2009 doi arXiv

  38. [46]

    Xiao, A note on vertex cover in graphs with maximum degree 3, in Computing and Com- binatorics, Springer, 2010, pp

    M. Xiao, A note on vertex cover in graphs with maximum degree 3, in Computing and Com- binatorics, Springer, 2010, pp. 150–159, https://doi.org/10.1007/978-3-642-14031-0_18

    2010 doi

  39. [47]

    Xiao and H

    M. Xiao and H. Nagamochi , Confining sets and avoiding bottleneck cases: A simple max- imum independent set algorithm in degree-3 graphs, Theor. Comput. Sci., 469 (2013), pp. 92–104, https://doi.org/10.1016/j.tcs.2012.09.022

    2013 doi

  40. [48]

    Xiao and H

    M. Xiao and H. Nagamochi , Exact algorithms for maximum independent set, Inf. Comput., 255 (2017), pp. 126–146, https://doi.org/10.1016/j.ic.2017.06.001. Appendix A. α-tensor and reducedα-tensor. The finite-valued entries ofα-tensor correspond to permissible configurations and...

    2017 doi

Pith tools

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