MISInstance

MISInstance#

class iqm.applications.mis.MISInstance(graph, penalty=1)[source]#

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 | int) – 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.

Attributes

best_quality

The best quality for the MIS problem, calculated using the Bron-Kerbosch algorithm.

Methods

fix_constraint_violation_bitstring(bit_str)

Postprocessing function that fixes a single bitstring, making it satisfy the constraints.
property best_quality: float#

The best quality for the MIS problem, calculated using the Bron-Kerbosch algorithm.

Instead of brute-forcing over all possible bitstrings, this uses an exhaustive algorithm that finds the best solution more efficiently (although it also has exponential scaling).

fix_constraint_violation_bitstring(bit_str)[source]#

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