Tutorial 2 - GreedyMIS Example Use Case¶

This notebook demonstrates how to solve the Maximum Independent Set (MIS) problem using the GreedyMIS algorithm provided by the MIS library. In this notebook, we present different solving modes:

• Classical solver
• Classical solver with greedy decomposition
• Quantum solver
• Quantum solver with greedy decomposition

Introduction to GreedyMIS¶

The GreedyMIS algorithm is a heuristic strategy for solving the Maximum Independent Set (MIS) problem by decomposing a graph into smaller subgraphs and solving each part either classically or using a QPU. Results for subgraphs are then aggregated for the final solution in the original graph. This approach is particularly valuable for two reasons:

• it supports parallelization, if you have access to several quantum devices or to a single device that can perform several distinct computations concurrently;
• it can be used to tailor the graph to hardware-constrained systems such as Rydberg atom arrays, where only specific subgraphs (e.g., unit-disk graphs) can be embedded and solved natively.\n",

How Subgraphs Are Created: Subgraphs are generated by greedily mapping the original graph onto a physical layout. Starting from different nodes, the algorithm assigns graph nodes to layout positions while preserving adjacency. This produces small, embeddable subgraphs used for solving MIS locally.

How Results Are Aggregated: The global MIS is built by combining independent subgraph solutions. After each subgraph MIS is selected, it is added to the global solution, and its nodes and neighbors are removed. The best solution maximizes total size of the global MIS.

Benefits¶

• Decomposes large graphs into smaller, embeddable subgraphs — especially useful when the full graph is too large to be solved directly on a QPU.
• While not guaranteed to be optimal, GreedyMIS often yields high-quality solutions faster than exact algorithms.
• Supports both classical and quantum solvers, allowing hybrid strategies that exploit quantum resources efficiently.
• Offers control through parameters like default_solving_threshold, subgraph_quantity, and mis_sample_quantity to fine-tune trade-offs between speed and solution quality.

Note¶

As of this writing, the package has been tested with unweighted graphs. Adding full-fledged functionality for weighted graphs is in progress.

Generating a random graph and basic parameters for greedy algorithm.

In [1]:

from mis.shared.types import MISInstance, MethodType
from mis.pipeline.config import BackendConfig, BackendType, SolverConfig, GreedyConfig
from mis import MISSolver
from mis.shared.graphs import is_independent

from mis.shared.types import MISInstance, MethodType from mis.pipeline.config import BackendConfig, BackendType, SolverConfig, GreedyConfig from mis import MISSolver from mis.shared.graphs import is_independent

In [2]:

from networkx import erdos_renyi_graph

# User can fix the seed for reproducibility 
seed = 0
graph = erdos_renyi_graph(n=25, p=0.4, seed=seed)

from networkx import erdos_renyi_graph # User can fix the seed for reproducibility seed = 0 graph = erdos_renyi_graph(n=25, p=0.4, seed=seed)

1. Classical Solver¶

This method uses a basic classical (eager) solver that attempts to compute the MIS solution directly on the full graph. It works well for small or sparse graphs, but becomes computationally intractable for larger, denser graphs due to the combinatorial complexity of the MIS problem.

Note: The solution size reflects the total numbers of nodes of the maximum independent set (MIS). Thus, the solution size equals the cardinality (size) of the independent set.

In [3]:

instance = MISInstance(graph)

config = SolverConfig(method=MethodType.EAGER)
solver = MISSolver(instance, config)
solution = solver.solve()[0]

print("Classical MIS (no greedy):", solution.nodes)
print("Solution size:", solution.size)
print("Independence check: ", is_independent(instance.graph, solution.nodes))
solution.draw()

instance = MISInstance(graph) config = SolverConfig(method=MethodType.EAGER) solver = MISSolver(instance, config) solution = solver.solve()[0] print("Classical MIS (no greedy):", solution.nodes) print("Solution size:", solution.size) print("Independence check: ", is_independent(instance.graph, solution.nodes)) solution.draw()

Classical MIS (no greedy): [0, 3, 7, 9, 11, 14, 23, 24]
Solution size: 8
Independence check:  True

2. Classical Solver with Greedy Decomposition¶

In this greedy method, the graph is first decomposed into smaller subgraphs using a greedy mapping strategy. These subgraphs are created by embedding parts of the graph onto a layout (e.g., a layout), enabling efficient and localized solving.

The default parameters in GreedyConfig are used to control how the decomposition works. Once the subgraphs are extracted, the MIS is solved separately on each one using the classical solver. The results are then merged recursively to build an overall solution.

This approach is especially useful for handling large or complex graphs, where solving the full graph at once is not practical.

In [4]:

config = SolverConfig(method=MethodType.GREEDY)
solver = MISSolver(instance, config)
solution = solver.solve()[0]

print("Classical MIS (greedy):", solution.nodes)
print("Solution size:", solution.size)
print("Independence check: ", is_independent(instance.graph, solution.nodes))
solution.draw()

config = SolverConfig(method=MethodType.GREEDY) solver = MISSolver(instance, config) solution = solver.solve()[0] print("Classical MIS (greedy):", solution.nodes) print("Solution size:", solution.size) print("Independence check: ", is_independent(instance.graph, solution.nodes)) solution.draw()

Classical MIS (greedy): [3, 21, 7, 23, 14, 11, 24]
Solution size: 7
Independence check:  True

Configuration Parameters¶

For customization of the GreedyMIS algorithm, a GreedyConfig object can be provided to the greedy parameter in SolverConfig.

• default_solving_threshold (int): Sets a default size threshold for subgraphs. If a subgraph has fewer nodes than this threshold, it will be solved using an default solver.
• subgraph_quantity (int): Determines how many different greedy decompositions (mappings) of the original graph should be attempted. More subgraphs can improve solution quality by increasing coverage and diversity, but will increase total computation time.
• mis_sample_quantity (int): Used in quantum solving mode. Specifies how many samples to draw from the quantum solver per subgraph.

In [5]:

config = SolverConfig(method=MethodType.GREEDY, greedy=GreedyConfig(default_solving_threshold=20, subgraph_quantity=10))
solver = MISSolver(instance, config)
solution = solver.solve()[0]

print("Classical MIS (greedy):", solution.nodes)
print("Solution size:", solution.size)
print("Independence check: ", is_independent(instance.graph, solution.nodes))
solution.draw()

config = SolverConfig(method=MethodType.GREEDY, greedy=GreedyConfig(default_solving_threshold=20, subgraph_quantity=10)) solver = MISSolver(instance, config) solution = solver.solve()[0] print("Classical MIS (greedy):", solution.nodes) print("Solution size:", solution.size) print("Independence check: ", is_independent(instance.graph, solution.nodes)) solution.draw()

Classical MIS (greedy): [21, 3, 11, 2, 7, 15, 19]
Solution size: 7
Independence check:  True

3. Quantum Solver¶

This mode uses a quantum backend (e.g., QutipBackend) to solve the MIS problem directly on the full graph. Quantum solving is suitable for small graphs or subgraphs, where the quantum device can fully embed the problem.

Quantum solvers do not return a single deterministic solution — instead, they return a distribution of possible solutions, each with an associated probability (or frequency). When you call solver.solve(), it returns a list of candidate solutions, typically ordered by frequency. So:

• result[0] corresponds to the most frequently observed (i.e. most probable) solution from the quantum sampling process.
• This behavior reflects the inherent probabilistic nature of quantum algorithms, where sampling repeatedly from the solution space allows you to statistically infer the best candidate.

For more details on how the quantum solver works, see the dedicated tutorial here - Using a Quantum Device to solve MIS

In [6]:

backend_config = BackendConfig(
    backend=BackendType.QUTIP
)
config = SolverConfig(method=MethodType.EAGER, backend=backend_config)
solver = MISSolver(instance, config)
solution = solver.solve()[0]

print("Quantum MIS (no greedy):", solution.nodes)
print("Solution size:", solution.size)
print("Independence check: ", is_independent(instance.graph, solution.nodes))
solution.draw()

backend_config = BackendConfig( backend=BackendType.QUTIP ) config = SolverConfig(method=MethodType.EAGER, backend=backend_config) solver = MISSolver(instance, config) solution = solver.solve()[0] print("Quantum MIS (no greedy):", solution.nodes) print("Solution size:", solution.size) print("Independence check: ", is_independent(instance.graph, solution.nodes)) solution.draw()

Quantum MIS (no greedy): [0, 3, 7, 9, 11, 14, 23, 24]
Solution size: 8
Independence check:  True

4. Quantum Solver with Greedy Decomposition¶

We combine quantum solving with greedy graph decomposition. Instead of solving the entire graph at once, we:

• Break the graph into smaller subgraphs using a greedy layout-based mapping.
• Solve each subgraph using the quantum backend.
• Recombine subgraph solutions recursively to form a global solution.
• Return the final "best guess" MIS solution

This allows solving larger graphs by breaking them into quantum-executable pieces.

Just like in the basic quantum solver, each subgraph is solved via quantum sampling. And for each subgraph, we get the is the most likely MIS configuration found by the quantum solver. Because each subgraph may produce slightly different outputs on each run (due to quantum randomness), this strategy naturally supports sampling multiple solutions and aggregating them to build diverse, high-quality approximations of the MIS. Thus, result[0] for the greedy solution is the "best guess" according to quantum sampling.

In [7]:

config = SolverConfig(
    method=MethodType.GREEDY,
    backend=backend_config,
)
solver = MISSolver(instance, config)
solution = solver.solve()[0]

print("Quantum MIS (greedy):", solution.nodes)
print("Solution size:", solution.size)
print("Independence check: ", is_independent(instance.graph, solution.nodes))
solution.draw()

config = SolverConfig( method=MethodType.GREEDY, backend=backend_config, ) solver = MISSolver(instance, config) solution = solver.solve()[0] print("Quantum MIS (greedy):", solution.nodes) print("Solution size:", solution.size) print("Independence check: ", is_independent(instance.graph, solution.nodes)) solution.draw()

Quantum MIS (greedy): [0, 3, 7, 9, 11, 14, 22, 23]
Solution size: 8
Independence check:  True

You can fine-tune the decomposition process using:

• default_solving_threshold: size of the solve small subgraphs to solve directly.
• subgraph_quantity: how many greedy mappings to try
• mis_sample_quantity: number of samples (if quantum solving is enabled)

In [8]:

config = SolverConfig(method=MethodType.GREEDY, backend=backend_config, greedy=GreedyConfig(default_solving_threshold=20, subgraph_quantity=10))
solver = MISSolver(instance, config)
solution = solver.solve()[0]

print("Quantum MIS (greedy):", solution.nodes)
print("Solution size:", solution.size)
print("Independence check: ", is_independent(instance.graph, solution.nodes))
solution.draw()

config = SolverConfig(method=MethodType.GREEDY, backend=backend_config, greedy=GreedyConfig(default_solving_threshold=20, subgraph_quantity=10)) solver = MISSolver(instance, config) solution = solver.solve()[0] print("Quantum MIS (greedy):", solution.nodes) print("Solution size:", solution.size) print("Independence check: ", is_independent(instance.graph, solution.nodes)) solution.draw()

Quantum MIS (greedy): [0, 3, 7, 9, 11, 14, 23, 24]
Solution size: 8
Independence check:  True