greedy_mis

Contents

greedy_mis#

iqm.applications.mis.greedy_mis(mis_problem, seed=None)[source]#

Standard greedy algorithm for maximum independent set problem class.

Steps:

  1. Pick the lowest-degree node in the graph (break ties randomly).

  2. Add it to the independent set.

  3. Remove it and all its neighbors from the graph.

  4. Repeat steps 1-3 until the graph is empty.

  5. Return the independent set.

Parameters:

  • mis_problem (MISInstance) – A problem instance of maximum independent set to be solved (approximately).

  • seed (int | None) – Optional seed for randomly breaking ties.

Returns:

A bitstring solution.

Return type:

str

Contents