Introduction¶

Currently, considerable efforts must be put to find optimal solution for NP-Hard 4 problems. Reoptimisation deals with, If given an optimal solution to a problem instance \(I_O\), can we find a good approximated solution to instance \(I_N\), where \(I_N\) is \(I_O\) with some ‘local’ modifications? The goal is to expose some well known reoptimization algorithms. Some references 1 2 3.

1: Escoffier, B., Bonifaci, V., Ausiello, G.: Complexity and approximation in reoptimization (02 2011), <https://doi.org/10.1142/9781848162778_0004>
2: Vazirani, V.V.: Approximation algorithms. Springer (2001) <https://www.ics.uci.edu/~vazirani/book.pdf>
3: Wikipedia: Approximation algorithms
4: Wikipedia: NP-Hard

Setup¶

Requirements¶

(Recommended) Python versions: >=3.6, <=3.9.*

Installation¶

Option 1

To Install the stable latest package from pypi host

pip install reoptimization-algorithms
Option 2

To install directly from source execute the following in source root directory

python setup.py install

Usage¶

Implementation basically consists of

Having a graph data structure utility
Implementing the respective graph algorithm methods

Graph Data structure¶

A graph \(G\) is a pair of sets \((V, E)\), where \(V\) is the set of vertices and \(E\) is the set of edges formed by pairs of vertices in \(V\)
An unordered graph is a graph where \(E\) is formed by unordered pairs of vertices
We consider path as ordered set of vertices where adjacent vertices forms an edge and by path length we refer as number of vertices in it
We say a set of vertices covers a path if at least one vertex from the set belongs to the set of the vertices in the path

The graph data structure implementation here is based on an adjacency list representation.
The adjacency structure is implemented as a Python dictionary of dictionaries, the outer dictionary is keyed by vertices and mapped to neighboring vertex forming an edge.
Vertices and Edges are provided with a weight property
Supports CRUD operations on vertices and edges of graph
References 5 6 7

5: Introduction to Graph Theory. Prentice Hall (1996)
6: Wikipedia: Graph Theory
7: Wikipedia: Adjacency list

Graph utilities

Graph - Graph utilities class

Undirected Graph - Undirected utilities class

Vertex - Vertex utilities class

Edge - Edge utilities class

Algorithms¶

Reoptimization of k Path vertex cover problems (k-PCVP)¶

The objective in k Path vertex cover problem is to compute a minimum subset \(S\) of the vertices in a graph \(G\) such that \(S\) covers all the paths of length \(k\) in the graph

Note k-PVCP will be referred as minimum k-PVCP throughout the package

PTAS for unweighted k-PVCP under constant size graph insertion 8 ¶

PTAS 9 algorithm when a constant size graph is inserted to the old graph. By constant graph we mean a graph having constant number of vertices.

8: Kumar M., Kumar A., Pandu Rangan C. (2019) Reoptimization of Path Vertex Cover Problem. In: Du DZ., Duan Z., Tian C. (eds) Computing and Combinatorics. COCOON 2019. Lecture Notes in Computer Science, vol 11653. Springer, Cham <https://link.springer.com/chapter/10.1007/978-3-030-26176-4_30>
9: Wikipedia: PTAS

UnweightedPVCP.reoptimize_ptas - Method to perform the algorithm

k-PVCP utilities¶

Some utilities for k path vertex cover

PVCUtils.is_k_pvc - Method to check if a vertex set is a valid k path vertex cover
PVCUtils.is_vertex_set_path - Method to check if a vertex set forms a path in the graph
PVCUtils.is_path - Method to check if a path exists in the graph

Package documentation¶

reoptimization_algorithms

Package implementing some well known Reoptimization algorithms

Contribution¶

Want to add or improvise the repository? Check out the Contributing documentation :)

Change Logs¶

For change logs refer to Updating documentation