# set_cover ## Abstract#

The Set Cover problem is one of the problems in graph theory that tries to solve the least possible set of sets that covers all elements inside those sets. Given a set of n elements, and a collection of m sets containing them, the algorithm tries to identify the smallest sub-collection of sets whose union equal to all the elements. It is NP-complete, however solvable with techniques such as constraint programming. The current algorithm uses GEKKO optimizer as a constraint programming solver.

TraitValue
Module typemodule
ImplementationPython
Graph directionundirected
Edge weightsunweighted
Parallelismsequential

## Procedures#

### `cp_solve(element_vertexes, set_vertexes)`#

#### Input#

The input itself represents an element-set pair with each row of the lists.

• `element_vertexes: List[Vertex]` ➡ List of element nodes in pairs
• `set_vertexes: List[Vertex]` ➡ List of set nodes in pairs

#### Output#

• `containing_set` ➡ minimal set of sets in which all the elements are contained

#### Usage#

``CALL set_cover.cp_solve([(:Point), (:Point)], [(:Set), (:Set)])YIELD containing_set;``

## Example# ## `greedy(context, element_vertexes, set_vertexes)`#

#### Input#

The input itself represents an element-set pair with each row of the lists.

• `element_vertexes: List[Vertex]` ➡ List of element nodes in pairs
• `set_vertexes: List[Vertex]` ➡ List of set nodes in pairs

#### Output#

• `containing_set` ➡ minimal set of sets in which all the elements are contained

#### Usage#

``CALL set_cover.greedy([(:Point), (:Point)], [(:Set), (:Set)])YIELD containing_set;``