Heuristic Algorithms For The Label Cut Problem Based On Random Depth First Search

The label cut problem is a class of classical combinatorial optimization problems defined on the label graph.Label graph consists of a vertex set,an edge set,a label set and a mapping from the edge set to the label set.In algorithm research,the label cut problem is a generalization of the corresponding optimization problem on general graphs;In practical applications,it is used to,e.g.,measure the robustness of the shared risk link networks.The minimum s-t label cut problem is the basic problem in the label cut problem.The goal is to find a minimum label subset on the label graph,so that after the edge set corresponding to the subset is deleted,the vertices s and t are no longer connected.The minimum s-t label cut problem,on the one hand,is a generalization of the minimum s-t cut problem;on the other hand,it is a sub-problem of the minimum s-t weighted label cut problem and the minimum label multi-cut problem.The minimum s-t label cut has been shown to be NP-hard,and there is no polynomial-time approximation algorithm with approximation ratio smaller than 2log1-1/loglogc n n(c<1/2)under the condition P≠ NP.However,There is a lack of heuristic algorithms that can provide good feasible solutions.This thesis systematically studies the heuristic algorithms for the minimum s-t label cut problem and related problems.To the best of our knowledge,this is the first work for the minimum s-t label cut problem from the aspect of heuristic algorithms.According to the characteristics and properties of the minimum s-t label cut problem,based on the idea of random walk and path sampling,this thesis proposes an evaluation function to quantify the influence factors of labels.The function runs multiple random depth-first searches,scoring each label based on the number of traversals through the label and the length of the path obtained for each traversal.The random depth-first search takes s as the starting vertex and t as the end vertex.During the traversal process,the next vertex is randomly selected according to the virtual weight of label on the edge(to distinguish the actual weight in the weighted label graph).Based on this evaluation function,this thesis designs a heuristic algorithm for the minimum s-t label cut problem.The algorithm is divided into three stages as follows.In the first stage,multiple label graphs with different virtual label weights are randomly generated according to the input label graph.In the second stage,a sub-algorithm is applied on each generated label graph,which evaluates labels,selects the optimal label as a part of the feasible solution,and delete the edge set corresponding to this label until the vertices s and t on the graph are no longer connected.In the third stage,the heuristic algorithm selects the smallest one from all the found feasible solutions as the algorithm’s final solution.This thesis found that the algorithm is not only suitable for the minimum s-t label cut problem,but also can solve the minimum s-t weighted label cut problem by modifying the statistical method in the evaluation function,and solve the minimum label multi-cut problem by modifying the starting vertex and end vertex of the random depth-first traversal in the evaluation function.Through experimental comparison,it is found that the designed heuristic algorithms can obtain good feasible solutions on these problems.In addition,the number of virtual label graphs in the algorithm and the number of random depth-first search are parameters of the algorithm,which can be modified according to the actual problem scale and operating conditions.Moreover,since the processes of the algorithm on multiple randomly generated virtual label graphs are independent and does not interfere with each other,the algorithm can be accelerated by parallel computing with simple modification.