Skip to content

mis.pipeline.kernelization

source module mis.pipeline.kernelization

Classes

source class Kernelization(config: SolverConfig, graph: nx.Graph)

Bases : BasePreprocessor

Methods

  • preprocess — Run preprocessing steps on the graph.

  • rebuild — Expand from MIS solutions on a reduced graph obtained by preprocess() into solutions on the original graph.

  • is_independent — Determine if a set of nodes represents an independent set within a given graph.

source method Kernelization.preprocess() → nx.Graph

Run preprocessing steps on the graph.

This will reduce the size of the graph. Do not forget to call rebuild() to convert solutions on the reduced graph into solutions on the original graph!

source method Kernelization.rebuild(partial_solution: set[int]) → set[int]

Expand from MIS solutions on a reduced graph obtained by preprocess() into solutions on the original graph.

Parameters

  • partial_solution A solution on the reduced graph. Note that we do not — check that this solution is correct.

  • Returns — A solution on the original graph.

source method Kernelization.is_independent(nodes: list[int]) → bool

Determine if a set of nodes represents an independent set within a given graph.

Parameters

  • A list of nodes within the latest iteration of the graph.

source class BaseKernelization(config: SolverConfig, graph: nx.Graph)

Bases : BasePreprocessor, abc.ABC

Shared base class for kernelization.

Methods

  • rebuild — Rebuild a MIS solution to the original graph from a partial MIS solution on the reduced graph obtained by kernelization.

  • is_independent — Determine if a set of nodes represents an independent set within a given graph.

  • is_subclique — Determine whether a list of nodes represents a clique within the graph, i.e. whether every pair of nodes is connected.

  • node_weight — Return the weight of a single node.

  • subgraph_weight — Return the total weight of a subgraph.

  • is_maximum — Determine whether any neighbor of a node has a weight strictly greater than that node.

  • is_isolated_and_maximum — Determine whether a node is isolated and maximum, i.e. 1. this node + its neighbors represent a clique; AND 2. no node in the neighborhood has a weight strictly greater than node.

  • add_node — Add a new node with a unique index.

  • preprocess — Apply all rules, exhaustively, until the graph cannot be reduced further, storing the rules for rebuilding after the fact.

  • add_rebuilder — Store a rebuilder step to be called during rebuild().

  • initial_cleanup — One-time cleanup of nodes that are trivially useless, e.g. negative weights.

  • search_rule_neighborhood_removal — Weighted: If a node has a greater weight than all its neighbors together, remove the node (it will be part of the WMIS) and all its neighbors (they won't). Unweighted: Noop.

  • get_nodes_with_strictly_higher_weight — Return the nodes with a weight strictly higher than a give node.

  • apply_rule_isolated_node_removal — Remove an isolated node / store the rebuild operation.

  • search_rule_isolated_node_removal — Remove any isolated node (see is_isolated for a definition).

  • fold_three — Fold three nodes V, U and X into a new single node V'.

  • apply_rule_node_fold — Fold three nodes V, U and X into a new single node / store the rebuild operation.

  • search_rule_node_fold — If a node V has exactly two neighbors U and X and there is no edge between U and X, fold U, V and X and into a single node.

  • twin_category — Determine which operations we can perform on two twin nodes.

  • find_removable_twin — Find a twin of a node, i.e. another node with the same neighbors, and check what we can do with this node.

  • fold_twin — Fold two twins U and V into a single node V'.

  • apply_rule_twins_in_solution — Remove two twin nodes and their neighbors / store the rebuild operation.

  • apply_rule_twin_independent — Remove two twin nodes and their neighbors / store the rebuild operation.

  • search_rule_twin_reduction — If a node V and a node U have the exact same neighbors (which indicates that they're not nightbours themselves), we may be able to merge U, V and their neighborhoods into a single node.

  • search_rule_unconfined_and_diamond — Look for unconfined nodes, i.e. a category of nodes for which we can prove easily that they cannot be part of a solution.

source method BaseKernelization.rebuild(partial_solution: set[int]) → set[int]

Rebuild a MIS solution to the original graph from a partial MIS solution on the reduced graph obtained by kernelization.

source method BaseKernelization.is_independent(nodes: list[int]) → bool

Determine if a set of nodes represents an independent set within a given graph.

Returns

  • bool — True if the nodes in nodes represent an independent set within graph. False otherwise, i.e. if there's at least one connection between two nodes of nodes

source method BaseKernelization.is_subclique(nodes: list[int]) → bool

Determine whether a list of nodes represents a clique within the graph, i.e. whether every pair of nodes is connected.

source method BaseKernelization.node_weight(node: int) → float

Return the weight of a single node.

source method BaseKernelization.subgraph_weight(nodes: Iterable[int]) → float

Return the total weight of a subgraph.

source method BaseKernelization.is_maximum(node: int, neighbors: list[int]) → bool

Determine whether any neighbor of a node has a weight strictly greater than that node.

source method BaseKernelization.is_isolated_and_maximum(node: int) → bool

Determine whether a node is isolated and maximum, i.e. 1. this node + its neighbors represent a clique; AND 2. no node in the neighborhood has a weight strictly greater than node.

source method BaseKernelization.add_node(weight: float) → int

Add a new node with a unique index.

source method BaseKernelization.preprocess() → nx.Graph

Apply all rules, exhaustively, until the graph cannot be reduced further, storing the rules for rebuilding after the fact.

source method BaseKernelization.add_rebuilder(rebuilder: BaseRebuilder) → None

Store a rebuilder step to be called during rebuild().

source method BaseKernelization.initial_cleanup() → None

One-time cleanup of nodes that are trivially useless, e.g. negative weights.

source method BaseKernelization.search_rule_neighborhood_removal() → None

Weighted: If a node has a greater weight than all its neighbors together, remove the node (it will be part of the WMIS) and all its neighbors (they won't). Unweighted: Noop.

source method BaseKernelization.get_nodes_with_strictly_higher_weight(node: int, neighborhood: Iterable[int]) → list[int]

Return the nodes with a weight strictly higher than a give node.

Parameters

  • node : int — The main node.

  • neighborhood : Iterable[int] — The list of nodes in which to search for a weight strictly higher than node.

Returns

  • list[int] — A list (possibly empty) of nodes from neighborhood. All these nodes are guaranteed to have a weight strictly higher than that of node.

    In unweighted mode, this list is always empty.

source method BaseKernelization.apply_rule_isolated_node_removal(isolated: int) → None

Remove an isolated node / store the rebuild operation.

Parameters

  • isolated An isolated node. We do not re-check that it is isolated.

source method BaseKernelization.search_rule_isolated_node_removal() → None

Remove any isolated node (see is_isolated for a definition).

source method BaseKernelization.fold_three(v: int, u: int, x: int, v_prime: int) → None

Fold three nodes V, U and X into a new single node V'.

source method BaseKernelization.apply_rule_node_fold(v: Any, w_v: float, u: Any, w_u: float, x: Any, w_x: float) → None

Fold three nodes V, U and X into a new single node / store the rebuild operation.

Parameters

  • v, u, x — Three nodes. U and X MUST both be neightours of V. There MUST NOT be any edge between U and X.

  • w_v, w_u, w_x — The weight of nodes v, u, x. We MUST have w_u + w_x > w_v (always true in unweighted mode). We MUST have w_x <= w_v and w_u <= w_v (always true in unweighted mode).

source method BaseKernelization.search_rule_node_fold() → None

If a node V has exactly two neighbors U and X and there is no edge between U and X, fold U, V and X and into a single node.

source method BaseKernelization.twin_category(u: int, v: int, neighbors: list[int]) → _TwinCategory

Determine which operations we can perform on two twin nodes.

Parameters

  • - u, v — two distinct nodes with the same set of neighbors

  • - neighbors — the neighbors of u (or equivalently v)

source method BaseKernelization.find_removable_twin(v: int) → _Twin | None

Find a twin of a node, i.e. another node with the same neighbors, and check what we can do with this node.

Parameters

  • v : int — a node

  • Returns — A _Twin if any twin of v was found and it can be removed, None otherwise.

source method BaseKernelization.fold_twin(u: int, v: int, v_prime: int, u_neighbors: list[int]) → None

Fold two twins U and V into a single node V'.

Parameters

  • u, v — The nodes to fold.

  • v_prime : int — The new node, already created.

  • u_neighbors : list[int] — The neighbors of U (or equivalently of V).

source method BaseKernelization.apply_rule_twins_in_solution(v: int, u: int, neighbors_u: list[int]) → None

Remove two twin nodes and their neighbors / store the rebuild operation.

We use this rule when we know that the twins will always be part of the solution.

Parameters

  • u, v — The twin nodes.

  • neighbors_u : list[int] — The neighbors of U (or equivalently of V).

source method BaseKernelization.apply_rule_twin_independent(u: int, v: int, neighbors: list[int]) → None

Remove two twin nodes and their neighbors / store the rebuild operation.

We use this rule when U and V are independent, i.e. either all the neighbors are part of the solution or both U and V are part of the solution, but we don't yet know which.

Parameters

  • u, v — The twin nodes.

  • neighbors_u — The neighbors of U (or equivalently of V).

source method BaseKernelization.search_rule_twin_reduction() → None

If a node V and a node U have the exact same neighbors (which indicates that they're not nightbours themselves), we may be able to merge U, V and their neighborhoods into a single node.

Note: as of this writing, in unweighted mode, the heuristic works when there are exactly 3 neighbors.

source method BaseKernelization.search_rule_unconfined_and_diamond() → None

Look for unconfined nodes, i.e. a category of nodes for which we can prove easily that they cannot be part of a solution.

source class UnweightedKernelization(config: SolverConfig, graph: nx.Graph)

Bases : BaseKernelization

Apply well-known transformations to the graph to reduce its size without compromising the result.

This algorithm is adapted from e.g.

https://schulzchristian.github.io/thesis/masterarbeit_demian_hespe.pdf

Methods

source method UnweightedKernelization.add_node(weight: float) → int

Add a node with a weight of exactly 1.0.

Parameters

  • weight : float — MUST be 1.0 in unweighted mode.

Returns

  • int — The index of the new node.

source method UnweightedKernelization.is_maximum(node: int, neighbors: list[int]) → bool

Since all nodes have the same weight, no node has a strictly higher weight.

source method UnweightedKernelization.initial_cleanup() → None

One-time cleanup of nodes that are trivially useless, e.g. negative weights.

source method UnweightedKernelization.get_nodes_with_strictly_higher_weight(node: int, neighborhood: Iterable[int]) → list[int]

Since all nodes have the same weight, no node has a strictly higher weight.

source method UnweightedKernelization.search_rule_neighborhood_removal() → None

source method UnweightedKernelization.twin_category(u: int, v: int, neighbors: list[int]) → _TwinCategory

Determine which operations we can perform on two twin nodes.

Parameters

  • - u, v — two distinct nodes with the same set of neighbors

  • - neighbors — the neighbors of u (or equivalently v)

Returns

  • _TwinCategory — - CannotRemove if the number of neighbors is not exactly 3. - Independent if the neighbors are independent from each other. - InSolution otherwise.

source method UnweightedKernelization.aux_search_confinement(neighbors_S: set[int], S: set[int]) → _ConfinementAux | None

Attempt to find a neighbor U of S such that

  • there is exactly one node in S that is a neighbor of U;
  • the number of neighbors of U that are not neighbors of S is minimized.

source method UnweightedKernelization.apply_rule_unconfined(v: int) → None

source method UnweightedKernelization.unconfined_loop(v: int, S: set[int], neighbors_S: set[int]) → bool

Starting from a node V, attempt to determine whether it is unconfined.

Parameters

  • v The node we're examining.

  • S (inout) A set we're building to help determine whether v is unconfined. — Should initially be {v}, grown during each iteration.

  • neighbors_S (inout) The set of neighbors of all elements of S

Returns False if the work is over (we couldn't find any matching value).

source method UnweightedKernelization.search_rule_unconfined_and_diamond() → None

Look for unconfined nodes, i.e. nodes for which we can prove easily that they cannot be part of a solution.

source class WeightedKernelization(config: SolverConfig, graph: nx.Graph)

Bases : BaseKernelization

Methods

source method WeightedKernelization.add_node(weight: float) → int

Add a new node with a unique index.

Parameters

  • weight : float — A strictly positive weight.

  • Returns — The index of the new node.

source method WeightedKernelization.is_maximum(node: int, neighbors: list[int]) → bool

Determine whether any neighbor of a node has a weight strictly greater than that node.

source method WeightedKernelization.initial_cleanup() → None

One-time cleanup of nodes that are trivially useless, e.g. negative weights.

source method WeightedKernelization.get_nodes_with_strictly_higher_weight(node: int, neighborhood: Iterable[int]) → list[int]

Return the nodes with a weight strictly higher than a give node.

Parameters

  • node : int — The main node.

  • neighborhood : Iterable[int] — The list of nodes in which to search for a weight strictly higher than node.

Returns

  • list[int] — A list (possibly empty) of nodes from neighborhood. All these nodes are guaranteed to have a weight strictly higher than that of node.

source method WeightedKernelization.search_rule_unconfined_and_diamond() → None

Look for unconfined nodes, i.e. a category of nodes for which we can prove easily that they cannot be part of a solution.

As of this writing, we don't know how to detect unconfined nodes in weighted mode, so this step is a NOOP.

source method WeightedKernelization.neighborhood_weight(node: int) → float

Return the total weight of the neighbors of a node.

source method WeightedKernelization.apply_rule_neighborhood_removal(node: int) → None

Remove a node and its neighbors / store rebuild role.

source method WeightedKernelization.search_rule_neighborhood_removal() → None

If a node has a greater weight than all its neighbors together, remove the node and all its neighbors.

During rebuild, the node will always be part of the WMIS, the neighbors never will.

source method WeightedKernelization.twin_category(u: int, v: int, neighbors: list[int]) → _TwinCategory

Determine which operations we can perform on two twin nodes.

Parameters

  • - u, v — two distinct nodes with the same set of neighbors

  • - neighbors — the neighbors of u (or equivalently v)

Returns

  • _TwinCategory — If the total weight of U + V is at least as large of the total weight of the neighbors, we can always find a solution in which U and V both are, so InSolution. If the neighbors are independent and, naming X the neighbor with the smallest weight, if the weight of U + V + X is at least as large of the total weight of the neighbors, then there is always a solution in which either both U and V are, or all the neighbors are, so Independent. Otherwise, we don't have any specific preprocessing for these twins, so CannotRemove.

source class BaseRebuilder()

Bases : abc.ABC

The pre-processing operations attempt to remove edges and/or vertices from the original graph. Therefore, when we build a MIS for these reduced graphs (the "partial solution"), we may end up with a solution that does not work for the original graph.

Each rebuilder corresponds to one of the operations that previously reduced the size of the graph, and is charged with adapting the MIS solution to the greater graph.

Methods

source method BaseRebuilder.rebuild(partial_solution: set[int]) → None

source class RebuilderIsolatedNodeRemoval(isolated: int, higher: list[int])

Bases : BaseRebuilder

Methods

source method RebuilderIsolatedNodeRemoval.rebuild(partial_solution: set[int]) → None

source class RebuilderNodeFolding(v: int, u: int, x: int, v_prime: int)

Bases : BaseRebuilder

Methods

source method RebuilderNodeFolding.rebuild(partial_solution: set[int]) → None

source class RebuilderUnconfined()

Bases : BaseRebuilder

Methods

  • rebuild — By definition, unconfined nodes are never part of the solution, so rebuilding is a noop.

source method RebuilderUnconfined.rebuild(partial_solution: set[int]) → None

By definition, unconfined nodes are never part of the solution, so rebuilding is a noop.

source class RebuilderTwinIndependent(v: int, u: int, neighbors: list[int], v_prime: int)

Bases : BaseRebuilder

Invariants

  • V has exactly the same neighbors as U;
  • there is no self-loop around U or V (hence U and V are not neighbors);
  • there is no edge between any of the neighbors;
  • V' is the node obtained by merging U, V and the neighbors.

Methods

source method RebuilderTwinIndependent.rebuild(partial_solution: set[int]) → None

source class RebuilderTwinAlwaysInSolution(v: int, u: int)

Bases : BaseRebuilder

Invariants

  • V has exactly the same neighbors as U;
  • there is no self-loop around U;
  • there is at least one connection between two neighbors of U.

Methods

source method RebuilderTwinAlwaysInSolution.rebuild(partial_solution: set[int]) → None

source class RebuilderNeighborhoodRemoval(dominant_vertex: int)

Bases : BaseRebuilder

Methods

source method RebuilderNeighborhoodRemoval.rebuild(partial_solution: set[int]) → None