primal_dual.hpp File Reference

Primal-dual approximation algorithms for graph problems. More...

#include <algorithm>
#include <py2cpp/py2cpp.hpp>

Include dependency graph for primal_dual.hpp:

Go to the source code of this file.

Functions
template<typename Graph , typename C1 , typename C2 >
auto	min_vertex_cover_pd (const Graph &gra, C1 &cover, const C2 &weight)
	Minimum weighted vertex cover using primal-dual algorithm.
template<typename Graph , typename C1 , typename C2 >
auto	min_maximal_independant_set_pd (const Graph &gra, C1 &indset, C1 &dep, const C2 &weight)
	Minimum maximal independent set using primal-dual algorithm.

Detailed Description

Primal-dual approximation algorithms for graph problems.

This module implements primal-dual approximation algorithms for two fundamental graph optimization problems:

1. Minimum weighted vertex cover
2. Minimum maximal independent set

Both algorithms use the primal-dual paradigm which provides a 2-approximation guarantee for the vertex cover problem and good approximation ratios for the independent set problem.

Function Documentation

min_maximal_independant_set_pd()

template<typename Graph , typename C1 , typename C2 >

auto min_maximal_independant_set_pd	(	const Graph &	gra,
		C1 &	indset,
		C1 &	dep,
		const C2 &	weight
	)

Minimum maximal independent set using primal-dual algorithm.

This function implements a primal-dual approximation algorithm for the minimum maximal independent set problem. The algorithm builds an independent set while maintaining maximal property by covering dependent vertices.

The algorithm works by:

1. Maintaining gap values (dual variables)
2. Selecting vertices with minimum gap values
3. Marking selected vertices as independent
4. Marking neighbors as dependent
5. Updating gap values for remaining vertices

The algorithm maintains gap values \(y_v\) and selects vertices with minimum gap:

\[ \min_{v \in N[u]} y_v \]

where \(N[u]\) is the closed neighborhood of vertex \(u\). Gaps are updated: \(y_v \leftarrow y_v - \min_{k \in N[u]} y_k\).

Template Parameters

Graph	Type of the graph, must provide vertex iteration
C1	Type of independent/dependent set mapping (vertex -> bool)
C2	Type of weight mapping (vertex -> weight)

Parameters

[in]	gra	input graph
[in,out]	indset	independent set mapping (updated with solution)
[in,out]	dep	dependent set mapping (updated during algorithm)
[in]	weight	vertex weight mapping

Returns

auto total cost of the independent set

min_vertex_cover_pd()

template<typename Graph , typename C1 , typename C2 >

auto min_vertex_cover_pd	(	const Graph &	gra,
		C1 &	cover,
		const C2 &	weight
	)

Minimum weighted vertex cover using primal-dual algorithm.

This function implements a 2-approximation algorithm for the minimum weighted vertex cover problem. The algorithm maintains dual variables (gap values) and greedily selects vertices to cover edges.

The algorithm guarantees:

• Primal cost ≤ 2 × Dual cost
• 2-approximation ratio for the optimal solution

The primal-dual algorithm maintains dual variables (gaps) and satisfies:

\[ \sum_{v \in C} w_v \le 2 \sum_{v \in V} y_v \]

where \(C\) is the vertex cover, \(w_v\) are weights, and \(y_v\) are dual variables. Gap updates: \(y_u \leftarrow y_u - y_v\) for each selected edge \((u, v)\).

Template Parameters

Graph	Type of the graph, must provide edges() and edge iteration
C1	Type of cover mapping (vertex -> bool)
C2	Type of weight mapping (vertex -> weight)

Parameters

[in]	gra	input graph
[in,out]	cover	vertex cover mapping (updated with solution)
[in]	weight	vertex weight mapping

Returns

auto total cost of the vertex cover