Exact algorithm, Phase 3

[Isinlor]

We have pretty good algorithms already. This is:

• Greedy Algorithm
• Bron–Kerbosch algorithm
• Backtracking algorithm

Backtracking should easily take on tree, lines, circles, stars etc. so I don't think there is any need to play around with these.

Bron–Kerbosch provides us with maximum clique. This potentially could speed up backtracking algorithm if we pre color the maximum clique.

First of all we should look at the new graphs from Kelk with our visualization in game. Is there any visible structure?

We should probably setup tests to make sure that algorithms work fine and benchmark them to make sure that whatever we do we are actually faster.

What we should do with algorithms:

• Remove spurious vertices i.e. vertices not connected to anything
• If there are subgraphs that are not connected to each other consider them separately (what about if subgraphs have single connection?)
• For each subgraph or whole graph if there are no subgraphs:
  • try greedy algorithm (this one should work fast for any graph)
  • find maximum clique (not sure about speed of this in worse case)
  • compare lower / upper bound
  • keep maximum clique colored and try backtracking

[Isinlor]

01 Long lines and circles L: 3 U: 3 C: 3

02 L: 3 U: 6 C: timeout

03 Big&Small L: 6 U: 8 C: timeout

04 L: 4 U: 7 C: timeout

05 Too big (No visualization) L: 2 U: 2 C: 2

06 Needles L: 3 U: 3

07 Medusa L: 8 U: 12 C: timeout

08 Dense L: 98 U: 98 C: 98

09 L: 3 U: 7 C: timeout

10 Picasso L: 2 U: 4 C: timeout

11 Groups L: 15 U: 15 C: 15

12 Vertical & Horizontal Easier L: 2 U: 3 C: timeout

13 L: 9 U: 14 C: timeout

14 Vertical & Horizontal L: 3 U: 5 C: timeout

15 3 Siblings (they are connected!) L: 5 U: 10 C: timeout

16 Picasso v2 L: 3 U: 4 C: timeout

17 Easier Groups L: 8 U: 8 C: timeout

18 Separate graphs L: 10 U: 13 C: timeout

19 Stars L: 11 U: 11 C: 11

20 Shining Stars L: 8 U: 9 C: timeout

[Isinlor]

Useful program: https://gephi.org/

The program needs special file format: block3_2018_graph_net_format.zip

[Isinlor]

The exact algorithm in game works with:

• 01 (Chromatic Number: 3)
• 06 (Chromatic Number: 2)
• 17 (Chromatic Number: 8)

Does not work yet:

• 03
• 10

[Isinlor]

Nice overview of classical graph coloring algorithms: http://fileadmin.cs.lth.se/cs/personal/andrzej_lingas/k-m.pdf

[ghost]

a guide to graph coloring.pdf

[Seeeeeyo]

1-1

1-2

2-1

2-2

3

4

6

7

8

9

10-1

10-2

11

13

14

15

16

17

18

19

20-1

20-2

[Seeeeeyo]

Here are some of my research results.

Check for cycles in undirected graphs: https://www.geeksforgeeks.org/detect-cycle-in-an-undirected-graph-using-bfs/

Some interesting slides: http://cms.dm.uba.ar/academico/materias/2docuat2018/investigacion_operativa/2017/Coloreo.pdf

RLF algorithm: https://www.gerad.ca/~alainh/RLFPaper.pdf it's code: https://www.codeproject.com/Articles/88674/%2FArticles%2F88674%2FGraph-coloring-using-Recursive-Large-First-RLF-algfac

Check for a "star" topology: https://www.geeksforgeeks.org/check-if-the-given-graph-represents-a-star-topology/?fbclid=IwAR3s3MeQupVBc1dVsxGkhyZPxyNSfYR8n42BqMD4ax_kltbDCrm465xQp_U

Check if a graph is a bipartie (that would be surprising to have bipartie graph in this phase): https://www.geeksforgeeks.org/check-if-a-given-graph-is-bipartite-using-dfs/

Check for "bus" topology, we definitely need this one: https://www.geeksforgeeks.org/check-if-the-given-graph-represents-a-bus-topology/

Find the articulation points: https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Find the Bridges; I have to do more research on the Tarjan's algorithm and it's utility. https://www.geeksforgeeks.org/bridge-in-a-graph/ https://www.youtube.com/watch?v=thLQYBlz2DM

[ghost]

I've finished DSATUR and uploaded the files, here are the results I've got for the graphs