Approximation Algorithms¶

Graphina provides approximation algorithms for several NP-hard graph problems.

Traveling Salesman Problem (TSP)¶

Finds an approximate solution to the TSP (shortest tour visiting all nodes).

Greedy Algorithm¶

Constructs a tour by repeatedly visiting the nearest unvisited node.

use graphina::approximation::tsp::greedy_tsp;
use ordered_float::OrderedFloat;

// Weights must implementation Ord (use OrderedFloat for f64)
let g_ord = graph.convert::<OrderedFloat<f64>>();
if let Ok((tour, cost)) = greedy_tsp(&g_ord, start_node) {
    println!("Tour: {:?}, Cost: {}", tour, cost);
}

Vertex Cover¶

Finds a subset of nodes such that every edge in the graph is incident to at least one node in the subset.

use graphina::approximation::vertex_cover::min_vertex_cover;

let cover = min_vertex_cover(&graph);

Maximum Independent Set¶

Finds a set of nodes where no two nodes in the set are adjacent.

use graphina::approximation::independent_set::max_independent_set;

let set = max_independent_set(&graph);

Maximum Clique¶

Finds the largest subset of nodes where every node is connected to every other node in the subset.

use graphina::approximation::clique::max_clique;

let clique = max_clique(&graph);

Other Approximations¶

Average Clustering Coefficient¶

Estimates the average local clustering coefficient.

use graphina::approximation::clustering::average_clustering;

let avg_cc = average_clustering(&graph);

Local Node Connectivity¶

Approximates the local node connectivity between two nodes using repeated BFS.

use graphina::approximation::connectivity::local_node_connectivity;

let conn = local_node_connectivity(&graph, source, target);

Diameter Lower Bound¶

Approximates the diameter of the graph by sampling.

use graphina::approximation::diameter::approximate_diameter;

let diameter = approximate_diameter(&graph).unwrap();

Minimum Maximal Matching¶

Greedy approximation for minimum maximal matching.

use graphina::approximation::matching::min_maximal_matching;

let matching = min_maximal_matching(&graph);

Ramsey R(2, t)¶

Approximates the Ramsey number R(2, t) by finding a max clique and max independent set.

use graphina::approximation::ramsey::ramsey_r2;

let (clique, ind_set) = ramsey_r2(&graph);

Densest Subgraph¶

Finds a subgraph with maximum average degree using a greedy peeling strategy.

use graphina::approximation::subgraph::densest_subgraph;

let nodes = densest_subgraph(&graph, None);

Treewidth¶

Approximates treewidth using minimum degree or minimum fill-in heuristics.

use graphina::approximation::treewidth::{treewidth_min_degree, treewidth_min_fill_in};

let (tw, order) = treewidth_min_degree(&graph);
// or
let (tw, order) = treewidth_min_fill_in(&graph);