enumeration of minimal dominating sets

[jfraymond]

Goal: implement an algorithm enumerating the minimal dominating sets of a graph as described in https://arxiv.org/abs/1810.00789 .

Component: graph theory

Keywords: enumeration, dominating set

Author: Jean-Florent Raymond

Branch/Commit: 054a7bd

Reviewer: David Coudert

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

[jfraymond]

Branch: u/gh-jfraymond/enumeration_of_minimal_dominating_sets

[jfraymond]

comment:2

(work in progress)

[jfraymond]

Commit: a8a37b0

[fchapoton]

comment:3

just some comments

• Please avoid that : +from sage.all import *

• use the arxiv role for arxiv links :arxiv:`2022.01243`

• one blank line after INPUT:

[dcoudert]

comment:4

I don't think it's a good idea to define new neighbor iterators in this file.
It might be better to properly extend the functionalities of neighbors and neighbor_iterator.

Also, your method neighbors_of_a_set do the same as .vertex_boundary(), except that it returns a set instead of a list.

[embray]

comment:5

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[sagetrac-git]

Changed commit from a8a37b0 to 822cefa

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a2e8bff	Minor fixes in the docstrings + moved some neighbors iterator to `generic_graph` + using `vertex_boundary` instead of `neighbors_of_a_set`
e3f50fe	Moved `is_dominating` and `is_redundant` to `generic_graph`.
26fa01f	minor changes + removed the `import all` statement
822cefa	minor doctstr changes

[jfraymond]

comment:7

Thanks for the comments.

Currently I assume that the vertices of the input graph are sortable, in order for some procedure to have deterministic output, which is required for the correctness of the algorithm. The procedure removes vertices one by one in increasing order until a property is met.

Is there a fast and easy way to sort the vertices in any case, for instance using some integer used internally to represent a vertex? Otherwise I could define an arbitrary order at the beginning, but that looks cumbersome.
Or can I assume that .vertices() always returns the vertices in the same order? (I guess not.)

[jfraymond]

Author: Jean-Florent Raymond

[dcoudert]

comment:9

method _peel

• as you mix sets and lists in the output. Use sets only
• instead of set(G.vertices()), use set(G). No need to sort here
• peeling = [(None, G.vertices())] should be (None, set(G))], right ?
• while H.order() > 0: -> while H:

Some parts can be simplified like:

-            for L in tree_search(H, plng, dom, i + 1):
-                yield L
+            yield from tree_search(H, plng, dom, i + 1)

I'm really not in favor of adding new vertex iterators methods. Instead, you could add parameter closed=True/False to neighbor_iterator and vertex_boundary.

Now, concerning the sorting, and in view of your code, you could relabel your graph and use the mapping before returning the result. Then, you can sort integers safely if needed.

int_to_vertex = list(G)
vertex_to_int = {u: i for i, u in enumerate(int_to_vertex)}
G = G.relabel(perm=vertex_to_int)
...
for dom in tree_search(G, peeling, set(), 0):
    # we generate the leaves of the search tree that are descendant of (empty set, 0)
    yield dom[0], {int_to_vertex[i] for i in dom[1]}

[mantepse]

comment:10

If you want to, you could add the following sanity check:

sage: findstat([(G, sum(1 for _ in minimal_dominating_sets(G))) for n in range(6) for G in graphs(n)], depth=0) # optional - internet
0: (St001302: The number of minimally dominating sets of vertices of a graph., [], 52)

or, taking a bit longer,

sage: findstat("Graphs", lambda G: sum(1 for _ in minimal_dominating_sets(G)), depth=0) # optional - internet
0: (St001302: The number of minimally dominating sets of vertices of a graph., [], 1000)

[jfraymond]

comment:11

Thanks!
@dcoudert: as far as I know using yield from would make the code non compatible with python 2. Can we assume that everybody uses python 3 now?

[dcoudert]

comment:12

Right, it's working in Cython, but not in Python 2, a pity :(

[sagetrac-git]

Changed commit from 822cefa to 7a3a79a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f66030c	added a parameter 'closed' to neighbor_iterator to get rid of closed_neighborhood_iterator + fixed my own failing doctests + simplified is_dominating
b41b8e9	addressed the comments about _peel + fixed a bug I introduced in neighbor_iterator
0cfa03c	replaced calls to the function `closed_vertex_boundary` by direct calculations in order to removed the code of this function
05861f0	fixed minor bugs in my doctests or typos
7a3a79a	some polishing. The minimal_dominating_set function now returns wrong results, which I will investigate later.

[dcoudert]

comment:14

May be we should make a specific ticket for the neighbor iterators. If you agree, I can do it.

[jfraymond]

comment:15

Indeed, I did not think of that. Thanks for offering! Feel free to do it.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ffbb1ad	typos
4353445	Major changes (mostly in cand_ext_enum) resulting in code that seems to work now. Positively tested on all graphs up to 8 vertices.
6d07f4c	Removed the doctest with findstat as it seems currently incompatible with py3.
f4f2513	tree_search: docstring + removed debug asserts
951ee4d	simplified peelings as some data they contained (the last cell) was not useful
8cee876	tree_seach: docstring + cut long comments
710dd5f	simplified the parameters used by cand_ext_enum
0b59e78	examples + improved doctests

[sagetrac-git]

Changed commit from 7a3a79a to 0b59e78

[sagetrac-git]

Changed commit from 0b59e78 to 41b349e

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e4bb218	Polishing docstrings + added bibliography and examples
41b349e	implemented the suggested fix to deal with graphs whose vertices cannot be sorted

[sagetrac-git]

Changed commit from 41b349e to 7597f88

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7597f88

pep8

[embray]

comment:40

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

[dcoudert]

comment:41

There is a merge conflict with last beta.

[dcoudert]

comment:43

I can help solving the merge conflicts if needed

[dcoudert]

Reviewer: David Coudert

[dcoudert]

comment:44

I fixed the merge conflicts, applied the modifications proposed in #comment:39, and move all methods related to domination to the file domination.py. I pushed everything to a new branch in public so that you can modify it if needed.

Do you agree with these changes ?

---

New commits:

a61547c	trac #27424: fix merge conflict with 9.0.beta1
c937e57	trac #27424: review ticket
4454cc0	trac #27424: move dominating_set to domination.py

[dcoudert]

Changed commit from 900ebf0 to 4454cc0

[dcoudert]

Changed branch from u/gh-jfraymond/enumeration_of_minimal_dominating_sets to public/graphs/27424_domination

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4294f7d

minor changes in docstrings + added one example of dominating_set

[sagetrac-git]

Changed commit from 4454cc0 to 4294f7d

[sagetrac-git]

Changed commit from 4294f7d to 054a7bd

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

054a7bd

updated copyright info for the dominating_set function

[jfraymond]

comment:47

Thanks for the changes! (And sorry for the late relpy!)
I agree with all of them.
I made some minor changes in the docstrings.

[dcoudert]

comment:48

LGTM.

[fchapoton]

comment:49

9.0 is out

[vbraun]

Changed branch from public/graphs/27424_domination to 054a7bd