mis.pipeline.kernelization

module

mis.pipeline.kernelization

Classes

• Kernelization

• BaseKernelization — Shared base class for kernelization.

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

• WeightedKernelization

• BaseRebuilder — 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.

• RebuilderIsolatedNodeRemoval — Construct a rebuilder for isolated node removal.

• RebuilderNodeFolding

• RebuilderUnconfined

• RebuilderTwinIndependent

• RebuilderTwinAlwaysInSolution

• RebuilderNeighborhoodRemoval

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.

method

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!

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[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 list of solutions on the original graph.

method

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.

class

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

Bases : BasePreprocessor, abc.ABC

Shared base class for kernelization.

Methods

• rebuild — Rebuild one or more MIS solutions 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.

• get_isolation — 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 that is also maximal (see get_isolation 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.

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[int]]

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

method

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

method

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.

method

node_weight (node: int) → float

Return the weight of a single node.

method

subgraph_weight (nodes: Iterable[int]) → float

Return the total weight of a subgraph.

method

is_maximum (node: int, neighbors: list[int]) → bool

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

method

get_isolation (node: int) → _IsolationLevel

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.

method

add_node (weight: float) → int

Add a new node with a unique index.

method

preprocess () → nx.Graph

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

method

add_rebuilder (rebuilder: BaseRebuilder) → None

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

method

initial_cleanup () → None

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

method

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.

method

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.

method

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.

method

search_rule_isolated_node_removal () → None

Remove any isolated node that is also maximal (see get_isolation for a definition).

method

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'.

method

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

method

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.

method

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)

method

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.

method

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

method

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

method

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

method

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.

method

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.

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

• add_node — Add a node with a weight of exactly 1.0.

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

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

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

• search_rule_neighborhood_removal

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

• aux_search_confinement

• apply_rule_unconfined

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

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

method

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.

method

is_maximum (node: int, neighbors: list[int]) → bool

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

method

initial_cleanup () → None

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

method

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.

method

search_rule_neighborhood_removal () → None

method

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.

method

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.

method

apply_rule_unconfined (v: int) → None

method

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

method

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.

class

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

Bases : BaseKernelization

Methods

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

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

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

• get_nodes_with_strictly_higher_weight — Return the nodes with a weight strictly higher than a give 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.

• neighborhood_weight — Return the total weight of the neighbors of a node.

• apply_rule_neighborhood_removal — Remove a node and its neighbors / store rebuild role.

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

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

method

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.

method

is_maximum (node: int, neighbors: list[int]) → bool

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

method

initial_cleanup () → None

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

method

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.

method

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.

method

neighborhood_weight (node: int) → float

Return the total weight of the neighbors of a node.

method

apply_rule_neighborhood_removal (node: int) → None

Remove a node and its neighbors / store rebuild role.

method

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.

method

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.

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

• rebuild

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[int]]

class

RebuilderIsolatedNodeRemoval (kernelization: BaseKernelization, isolated: int)

Bases : BaseRebuilder

Construct a rebuilder for isolated node removal.

Parameters

• - kernelization — The kernelizer at the time we construct the rebuilder (before removing any node). We store a deep copy of the kernelizer until rebuilding.

• - isolated — The isolated node we have detected. The neighborhood of this node MUST be a clique. We expect that the neighborhood of this node and the node itself will be removed just after creating this rebuilder.

Methods

• rebuild — Expand the solution.

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[int]]

Expand the solution.

Note that we do not expect self.isolated to be the only isolated node within the clique, as this would cause us to lose potential solutions, see e.g. issue #135.

class

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

Bases : BaseRebuilder

Methods

• rebuild

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[int]]

class

RebuilderUnconfined ()

Bases : BaseRebuilder

Methods

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

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[int]]

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

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

• rebuild

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[int]]

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

• rebuild

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[int]]

class

RebuilderNeighborhoodRemoval (dominant_vertex: int)

Bases : BaseRebuilder

Methods

• rebuild

method

rebuild (partial_solution: frozenset[int]) → list[frozenset[int]]