greedy_mwis#
- iqm.applications.mis.greedy_mwis(mwis_problem, seed=None)[source]#
Compute an approximation to the maximum-weight independent set using a greedy heuristic.
This function approximates a Maximum Weight Independent Set (MWIS) by computing a greedy minimum-weight vertex cover on a copy of the input graph and returning its complement. Node weights are interpreted according to the same attribute-priority convention used by
MaximumWeightISInstance(seeNODE_ATTR_PRIORITY).- Parameters:
mwis_problem (MaximumWeightISInstance) – MWIS Instance which we’re trying to solve.
seed (int | None) – Optional random seed used to break ties reproducibly during the greedy selection process.
- Returns:
A bitstring encoding the selected independent set.
- Return type: