mis.pipeline.kernelization

source module mis.pipeline.kernelization

Classes

BaseKernelization — Shared base class for kernelization.
Kernelization — Apply well-known transformations to the graph to reduce its size without compromising the result.
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
RebuilderNodeFolding
RebuilderUnconfined
RebuilderTwinIndependent
RebuilderTwinHasDependency

source class BaseKernelization(graph: nx.Graph)

Bases : BasePreprocessor, abc.ABC

Shared base class for kernelization.

Methods

preprocess
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.
is_isolated — Determine whether a node is isolated, i.e. this node + its neighbours represent a clique.

source method BaseKernelization.preprocess() → nx.Graph

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.is_isolated(node: int) → bool

Determine whether a node is isolated, i.e. this node + its neighbours represent a clique.

source class Kernelization(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

preprocess — Apply all rules, exhaustively, until the graph cannot be reduced further, storing the rules for rebuilding after the fact.
apply_rule_isolated_node_removal
search_rule_isolated_node_removal — Remove any isolated node (see is_isolated for a definition).
apply_rule_node_fold
search_rule_node_fold — If a node V has exactly two neighbours U and X and there is no edge between U and X, fold U, V and X and into a single node.
aux_search_confinement
apply_rule_unconfined
unconfined_loop
search_rule_unconfined_and_diamond
fold_twin
find_twin — Find a twin of a node, i.e. another node with the same neighbours.
apply_rule_twin_independent
apply_rule_twin_has_dependency
search_rule_twin_reduction — If a node has exactly 3 neighbours and a twin (another node with the exact same neighbours), we can merge the 5 nodes.

source method Kernelization.preprocess() → nx.Graph

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

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

source method Kernelization.search_rule_isolated_node_removal() → None

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

source method Kernelization.apply_rule_node_fold(v: int, u: int, x: int) → None

source method Kernelization.search_rule_node_fold() → None

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

source method Kernelization.aux_search_confinement(neighbors_S: set[int], S: set[int]) → tuple[int, int, set[int]]

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

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

source method Kernelization.search_rule_unconfined_and_diamond() → None

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

source method Kernelization.find_twin(v: int) → int | None

Find a twin of a node, i.e. another node with the same neighbours.

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

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

source method Kernelization.search_rule_twin_reduction() → None

If a node has exactly 3 neighbours and a twin (another node with the exact same neighbours), we can merge the 5 nodes.

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