Iterator over the distance-k dominating sets

[dcoudert]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Problem Description

Question 67263 on ask.sagemath.org asks for a method to list all minimal distance-k dominating sets of a graph.

Proposed Solution

To iterate over the minimal distance k dominating sets, we can modify the working copy of the graph in method minimal_dominating_sets, adding edges between vertices at distance at most k.

To iterate over minimum distance k dominating set, we can create a new method dominating_sets and use constraints generation to prevent finding twice a minimum dominating set.

Alternatives Considered

None.

Additional Information

The default value of parameter work_on_copy is True, and so by default the input graph is modified. This is a bad choice. We should at least change the default value to False.

[dcoudert]

With PR #35462, we can iterate over the minimal distance-k dominating sets, and with PR #35463 we can iterate over the minimum distance-k dominating sets.