reoptimization_algorithms.algorithms.unwtd_pvcp.UnweightedPVCP

class UnweightedPVCP

Bases: object

Class containing reoptimization algorithms of unweighted path vertex cover

static reoptimize_ptas(old_graph: reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph, attach_graph: reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph, attach_edges: List[reoptimization_algorithms.utils.graph.edge.Edge], old_solution: Set[str], k: int, epsilon: float = 0.25) → Set[str]

\((1+\epsilon)\) PTAS approximation for reoptimization of unweighted k path vertex cover under constant size graph insertion

For formalisms and algorithm details refer 1

Parameters

  • old_graph (List[Edge]) – Old graph

  • attach_graph (UndirectedGraph) – Constant size graph which is to be inserted

  • attach_edges (List[Edge]) – Edges connecting the old graph and attach graph

  • old_solution (Set[str]) – Vertices denoting k-PVCP Solution to old graph

  • k (int) – length of paths to cover

  • epsilon (float, optional (default = 0.25)) – epsilon in \((1+\epsilon)\) PTAS approximation

Returns

Set of vertices

Example

import reoptimization_algorithms as ra

old_graph = (ra.UndirectedGraph().add_vertex("4").add_edge("4", "5").add_edge("40", "50")
             .add_vertex("6").add_edge("4", "8").add_vertex("99")
             .delete_vertex("6"))
attached_graph = ra.UndirectedGraph().add_edge("90", "95")
attach_edges = [ra.Edge("4", "90")]
old_solution = {"8"}

solution = ra.UnweightedPVCP.reoptimize_ptas(old_graph, attached_graph, attach_edges, old_solution, k = 3)
print(solution) # {"4"}

References

1

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>