OptimalBranchingMIS

measure(p::MISProblem, ::D3Measure)

Calculates the D3 measure for the given MISProblem, which is defined as the sum of the maximum degree of each vertex minus 2, for all vertices in the graph.

Arguments

• p::MISProblem: The problem instance containing the graph.

Returns

• Int: The computed D3 measure value.

measure(p::MISProblem, ::NumOfVertices)

Calculates the number of vertices in the given MISProblem.

Arguments

• p::MISProblem: The problem instance containing the graph.

Returns

• Int: The number of vertices in the graph.

reduce_problem(::Type{R}, p::MISProblem, ::MISReducer) where R

Reduces the given MISProblem by removing vertices based on their degrees and returns a new MISProblem instance along with the count of removed vertices.

Arguments

• p::MISProblem: The problem instance containing the graph to be reduced.
• ::MISReducer: An instance of the MISReducer struct.
• ::Type{R}: The type of the result expected.

Returns

• A tuple containing:
  • A new MISProblem instance with specified vertices removed.
  • An integer representing the count of removed vertices.

Description

The function checks the number of vertices in the graph:

• If there are no vertices, it returns an empty instance and a count of 0.
• If there is one vertex, it returns an empty instance and a count of 1.
• If there are two vertices, it returns an empty instance and a count based on the presence of an edge between them.
• For graphs with more than two vertices, it calculates the degrees of the vertices and identifies the vertex with the minimum degree to determine which vertices to remove.

closed_neighbors(g::SimpleGraph, vertices::Vector{Int})

Returns a set of vertices that includes the input vertices as well as their open neighbors.

Arguments

• g::SimpleGraph: The input graph.
• vertices::Vector{Int}: The vertices for which closed neighbors are to be computed.

Returns

A set of vertices that includes the input vertices as well as their open neighbors.

counting_mis1(g::SimpleGraph)

Calculates the maximum independent set (MIS) for a given SimpleGraph by first converting it into an EliminateGraph and then applying the counting_mis1 function.

Arguments

• g::SimpleGraph: The input graph for which the maximum independent set is to be calculated.

Returns

• MISCount: The size of the maximum independent set for the provided graph and the count of branches.

counting_mis2(g::SimpleGraph)

Calculates the size of the maximum independent set and the count of branches for a given SimpleGraph.

counting_xiao2013(g::SimpleGraph)

This function counts the maximum independent set (MIS) in a given simple graph using the Xiao 2013 algorithm.

Arguments

• g::SimpleGraph: A simple graph for which the maximum independent set is to be counted.

Returns

• CountingMIS: An object representing the size of the maximum independent set and the count of branches.

mis_branch_count(g::AbstractGraph; bs::BranchingStrategy = BranchingStrategy(table_solver = TensorNetworkSolver(), selector = MinBoundaryHighDegreeSelector(2, 6, 0), measure=D3Measure()), reducer=MISReducer())

Calculate the size and the number of branches of the Maximum Independent Set (MIS) for a given graph.

Arguments

• g::AbstractGraph: The graph for which the MIS size and the number of branches are to be calculated.
• bs::BranchingStrategy: (optional) The branching strategy to be used. Defaults to a strategy using table_solver=TensorNetworkSolver, selector=MinBoundaryHighDegreeSelector(2, 6, 0), and measure=D3Measure.
• reducer::AbstractReducer: (optional) The reducer to be applied. Defaults to MISReducer.

Returns

• A tuple (size, count) where size is the size of the Maximum Independent Set and count is the number of branches.

mis_size(g::AbstractGraph; bs::BranchingStrategy = BranchingStrategy(table_solver = TensorNetworkSolver(), selector = MinBoundaryHighDegreeSelector(2, 6, 0), measure=D3Measure()), reducer::AbstractReducer = MISReducer())

Calculate the size of the Maximum Independent Set (MIS) for a given graph.

Arguments

• g::AbstractGraph: The graph for which the MIS size is to be calculated.
• bs::BranchingStrategy: (optional) The branching strategy to be used. Defaults to a strategy using table_solver=TensorNetworkSolver, selector=MinBoundaryHighDegreeSelector(2, 6, 0), and measure=D3Measure.
• reducer::AbstractReducer: (optional) The reducer to be applied. Defaults to MISReducer.

Returns

• An integer representing the size of the Maximum Independent Set for the given graph.

neighbor_cover(g::SimpleGraph, v::Int, k::Int)

Compute the neighbor cover of a vertex in a graph.

Arguments

• g::SimpleGraph: The input graph.
• v::Int: The vertex for which to compute the neighbor cover.
• k::Int: The number of iterations to perform.

Returns

• vertices: An array containing the vertices in the neighbor cover.
• openvertices: An array containing the open vertices in the neighbor cover.

neighbors_2nd(g::SimpleGraph, v::Int)

Return the second-order neighbors of a vertex v in a simple graph g.

Arguments

• g::SimpleGraph: The simple graph.
• v::Int: The vertex.

Returns

• Array{Int}: An array of second-order neighbors of v.

open_neighbors(g::SimpleGraph, vertices::Vector{Int})

Returns a vector of vertices in the graph g, which are neighbors of the given vertices and not in the given vertices.

Arguments

• g::SimpleGraph: The graph in which to find the open neighbors.
• vertices::Vector{Int}: The vertices for which to find the open neighbors.

Returns

A vector of open neighbors of the given vertices.

open_vertices(g::SimpleGraph, vertices::Vector{Int})

Remove vertices from the given vector that are connected to all other vertices in the graph.

Arguments

• g::SimpleGraph: The graph object.
• vertices::Vector{Int}: The vector of vertices.

Returns

• Vector{Int}: The open vertices.

removed_vertices(vertices::Vector{Int}, g::SimpleGraph, clause::Clause{N}) where N

Given a list of vertices, a graph, and a clause, this function returns a list of removed vertices.

The vertices argument is a vector of integers representing the vertices to consider. The g argument is a SimpleGraph object representing the graph. The clause argument is a Clause object representing a clause.

The function iterates over the vertices and checks if the corresponding bit in the clause.mask is 1. If it is, the vertex is added to the list of removed vertices (rvs). If the corresponding bit in the clause.val is also 1, the neighbors of the vertex are also added to rvs.

The function returns the list of removed vertices with duplicates removed.

D3Measure

A struct representing a measure that calculates the sum of the maximum degree minus 2 for each vertex in the graph.

Fields

• None

struct MISCount

Represents the count of Maximum Independent Sets (MIS).

Fields

• mis_size::Int: The size of the Maximum Independent Set.
• mis_count::Int: The number of Maximum Independent Sets of that size.

Constructors

• MISCount(mis_size::Int): Creates a MISCount with the given size and initializes the count to 1.
• MISCount(mis_size::Int, mis_count::Int): Creates a MISCount with the specified size and count.

mutable struct MISProblem <: AbstractProblem

Represents a Maximum Independent Set (MIS) problem.

Fields

• g::SimpleGraph: The graph associated with the MIS problem.

Methods

• copy(p::MISProblem): Creates a copy of the given MISProblem.
• Base.show(io::IO, p::MISProblem): Displays the number of vertices in the MISProblem.

MISReducer

A struct representing a reducer for the Maximum Independent Set (MIS) problem. This struct serves as a specific implementation of the AbstractReducer type.

struct MinBoundaryHighDegreeSelector <: AbstractVertexSelector

The MinBoundaryHighDegreeSelector struct represents a strategy: - if exists a vertex with degree geq highdegreethreshold, then select it and its k-degree neighbors. - otherwise, select a subgraph with the minimum number of open vertices by k-layers of neighbors.

Fields

• kb::Int: The number of layers of neighbors to consider when selecting the subgraph.
• hd::Int: The threshold of degree for a vertex to be selected.
• kd::Int: The number of layers of neighbors to consider when selecting the subgraph.

struct MinBoundarySelector <: AbstractVertexSelector

The MinBoundarySelector struct represents a strategy for selecting a subgraph with the minimum number of open vertices by k-layers of neighbors.

Fields

• k::Int: The number of layers of neighbors to consider when selecting the subgraph.

NumOfVertices

A struct representing a measure that counts the number of vertices in a graph. Each vertex is counted as 1.

Fields

• None

TensorNetworkSolver
TensorNetworkSolver(; prune_by_env::Bool = true)

A struct representing a solver for tensor network problems. This struct serves as a specific implementation of the AbstractTableSolver type.