MISInstance

Module: iqm.applications.mis

class iqm.applications.mis.MISInstance(graph, penalty=1, allow_custom_var_names=False)

Bases: ISInstance

The instance class for maximum independent set problems.

The maximum independent set problem refers to finding the largest subset of nodes of a graph, such that no nodes in the subset are connected by an edge. It is completely equivalent to finding the largest clique on the complement graph. The class is initialized by initializing its parent class ISInstance with a simple objective function (aiming at maximizing the number of “selected” nodes).

Parameters:

• graph (Graph) – The Graph describing the MIS problem.

• penalty (float) – The penalty to be incurred per each edge present in the solution, sometimes referred to as \(\lambda\) in the literature. The higher it is, the less likely the algorithm is to include an edge in the solution. It needs to be set above 1 to insure that the solution is a maximum independent set. It’s typically set at 2. At 1, the correct solution will be degenerate with non-independent sets.

• allow_custom_var_names (bool) – Determines whether it’s allowed for graph to have nodes labelled by anything other than consecutive integers starting at 0.

Attributes

best_quality	The best quality for the MIS problem.
highest_quality_bitstrings	The worst bitstring for the MIS problem, determined trivially.
lower_bound	The lowest quality value among all possible bitstrings.
lowest_quality_bitstrings	The best bitstrings for the MIS problem.

Methods

fix_constraint_violation_bitstring	Postprocessing function that fixes a single bitstring, making it satisfy the constraints.
solve_with_bron_kerbosch	Solve the MIS problem using Bron-Kerbosch algorithm and save some properties of the solution.

property best_quality: float

The best quality for the MIS problem.

Can be calculated together with other properties of the solution using the exhaustive Bron-Kerbosch algorithm.

property lowest_quality_bitstrings: set[str]

The best bitstrings for the MIS problem.

Can be calculated together with other properties of the solution using the exhaustive Bron-Kerbosch algorithm.

property lower_bound: float

The lowest quality value among all possible bitstrings.

Can be calculated together with other properties of the solution using the exhaustive Bron-Kerbosch algorithm.

solve_with_bron_kerbosch()

Solve the MIS problem using Bron-Kerbosch algorithm and save some properties of the solution.

Return type:

None

property highest_quality_bitstrings: set[str]

The worst bitstring for the MIS problem, determined trivially.

The worst bitstring satisfying all constraints is always selecting no nodes.

fix_constraint_violation_bitstring(bit_str)

Postprocessing function that fixes a single bitstring, making it satisfy the constraints.

It works in the following way:

1. Get the subgraph induced by the bitstring bit_str.

2. Find the node with the highest degree.

3. Remove the node from the subgraph (i.e., flip the corresponding bit from “1” to “0”).

4. Repeat 2-3 until the subgraph contains no edges.

5. Return the bitstring corresponding to the remaining subgraph (which is an independent subset of the original graph).

For penalty = 1, this guarantees that the output bitstring has energy at least as low as the input bitstring. For penalty > 1, the energy is expected to be even lower.

Parameters:

bit_str (str) – The bitstring to be modified to satisfy the independence constraint.

Returns:

The modified bitstring, corresponding to an independent set of the problem graph.

Return type:

str

Inheritance