Implement Elser Numbers and Nucleus Complexes

[galen-dorp]

Create a module that computes

(1) the kth Elser number of a graph G

(2) the nucleus complex of a graph G for every subset of the vertices

(3) Betti numbers of these complexes

For definitions of these objects, see: https://doi.org/10.1016/j.jcta.2020.105364

As a side-effect of these computations, also define functions of possible general interest

(4) is_vertex_cover determines if L is a vertex cover of G (returns a boolean)

(5) all connected subgraphs of a graph G based on a suggestion from dcoudert, item 5 has been moved to its own ticket, see Ticket #32136

Depends on #32136

CC: @darijgr @kliem

Component: graph theory

Author: Galen Dorpalen-Barry

Branch/Commit: u/gh-galen-dorp/elser-numbers @ 859bcff

Issue created by migration from https://trac.sagemath.org/ticket/32047

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

e8d054e	changed some formatting in elser numbers file
00948cb	added the elser-numbers.py file to the all.py file
666abe9	modified the way the elser file was added into all.py
56d57c1	Removed the chain complex stuff, all doc tests passed.
908edc8	Added nucleus_complex method, all doc tests passed
ae2f536	Added all_nucleus_complexes. All doc tests pass.
6ad6754	Added the Betti number computations, all tests passed
c2a517f	Improved documentation
9a1d189	added references to the long references file and linked them to elser_numbers
859bcff	added documentation for the general interest functions

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: 859bcff

[videlec]

comment:3

Some remarks.

Your method connected_subgraphs_of suffer several problems.

• It has a strange name : I would simplify to connected_subgraphs.
• More importantly, there is an undesirable collision with connected_subgraph_iterator where a connected subgraph means a subset of vertices on which the induced graph is connected.
• I would rather implement an iterator rather than returning a list (this is quite standard that Python functions tend to return iterators rather than lists)
• Finally, such function could be optimized a lot using backtracking

Also in nuclei_by_size, why do you sort them by size? The size is easily recovered with len(G) (which is much faster than len(G.vertices())). If you just implement nuclei then the dictionary can be reconstructed in two lines

sage: G = # whatever
sage: by_size = {i: [] for i in range(len(G))}
sage: for N in G.nuclei(): by_size[len(N)].append(n)

Also, if I am not mistaken, to make your sum you don't need that dictionary as the Elser number is

return (-1)**(len(G)+1) * sum((-1)**len(N) * len(N)**k for N in G.nuclei())

[galen-dorp]

comment:5

Thanks for the comments! I changed the status to "needs work" so I can work on those changes!

[dcoudert]

comment:6

Actually, the connected subgraph part deserves a separate ticket. It's a significant amount of work and it's easier to review / correct / improve smaller tickets.

The difference with connected_subgraph_iterator is that you want all connected subgraphs and not only the induced connected subgraphs. So an option could be to add parameter induced to connected_subgraph_iterator, and then to switch to the appropriate method. And it's true that connected_subgraph_iterator could be renamed connected_subgraphs.

[dcoudert]

comment:7

I had a look at the paper and the code and I'm really worried about the efficiency of the proposed method. You need a more efficient way to enumerate nuclei (connected subgraphs of G such that V(G) is a vertex cover of G). The current brute force approach is ok for graphs with up to 10-12 nodes.

sage: G = graphs.Grid2dGraph(3, 4)                                                                                                                 
sage: %time G.elser_number(5)                                                                                                                      
CPU times: user 5.59 s, sys: 127 ms, total: 5.72 s
Wall time: 5.86 s
18264450
sage: G = graphs.CompleteGraph(7)                                                                                                                  
sage: %time G.elser_number(5)                                                                                                                      
CPU times: user 1min 56s, sys: 8.87 s, total: 2min 5s
Wall time: 2min 6s
5569200

Is the brute force approach the only way to compute this value ?

[galen-dorp]

comment:8

Thanks dcoudert for the comments! I'll separate the tickets and will work on your suggestion for adding an induced parameter to the existing connected_subgraph_iterator.

As for the timing issues, there are some small things that can be changed, but I'm not sure how much it will change the timing for arbitrary graphs. Given that, I'll hold off those changes for once everything else is working.

[galen-dorp]

Dependencies: 32136

[galen-dorp]

Description changed:

--- 
+++ 
@@ -12,4 +12,5 @@

 (4) is_vertex_cover determines if L is a vertex cover of G (returns a boolean)

-(5) all connected subgraphs of a graph G
+~~(5) all connected subgraphs of a graph G~~
+based on a suggestion from dcoudert, item 5 has been moved to its own ticket, see Ticket #32136

[mkoeppe]

comment:10

Setting a new milestone for this ticket based on a cursory review.