missing algorithms

[CarloLucibello]

Here is a partial list of missing algorithms. For hard problems (as most problems in this list) both exact and heuristic solvers should be implemented.

Problems not yet addressed in Erdos

• coloring for fixed q
• coloring number and optimal coloring
• maximum independent set (also known as vertex packing problem)
• maximum weight independent set (weights on vertices)
• minimum vertex cover
• graph isomorphism
  • fastest known exact algorithm is Algorithm 4 here https://arxiv.org/pdf/1607.00547.pdf
• prize collecting steiner tree
  • message passing heuristic https://arxiv.org/abs/1309.0346
• travelling salesman problem
• clique problems
• maximum weight b-matching
  • efficient exact solver (Edmond's)
  • linear programming as bootstrap for interger programming
  • message passing heuristic http://www.jmlr.org/proceedings/papers/v15/huang11a/huang11a.pdf

New algorithms for "old" problems

• Community Detection
  • SCoDA https://arxiv.org/pdf/1703.02955.pdf
• Matching
  • Hungarian Algorithm https://github.com/Gnimuc/Hungarian.jl

Most problems can be formulated as integer programming problems and solved (at least for small instances) through JuMP and generict IP solver.

Simulated Annealing could be implemented as a general heuristic solver.
See also https://github.com/carlobaldassi/RRRMC.jl.

For most problems message passing heuristics (belief propagation) can be found in the literature