Fixed-Parameter Tractable Algorithms For Three Graph Modification Problems

In this paper three NP-hard figure design of fixed parameters can be modified problem algorithm.The first problem is how to from a simple undirected graph node removes the least, make the rest of the degree of all the vertices in the graph is not greater than3. In previous the time complexity of fixed parameters can be given solution algorithm, first remove node of degrees is greater than3, then process both directly connected degree is3nodes, considering the two nodes neighbors, and this kind of situation will tell many seeds, which they all four neighbor nodes is1of that kind of situation is the most complex, the processing degree of3nodes. Based on this algorithm is one of the most complicated situations, by considering the two nodes subdividing neighbor to neighbor nodes, and the breakdown of each case individually treatment:according to the analysis of deleting the least node makes the situation meet conditions, finally reduced the time complexity to O*(3.1*).The second question is how to from the given to delete the least amount of nodes in the directed graph, makes the rest of the graph of each of the nodes and the degrees are less than2. This article uses the limited depth of the search tree technology can be fixed parameters algorithm is designed. The algorithm first delete out and into the degrees are greater than3nodes, and then analysis the rest of the graph, through the degree and the degree of value to deal with, because the degrees of indegree values for the3biggest, so there are a total of seven. And gives the corresponding processing for each case:remove the least nodes make the situation out and into the degrees are accord with the requirement of less than or equal to1. The time complexity of the algorithm is O*(3k).The third problem is how to deleted from the undirected graph of a given minimum edge, after the rest of the figure of two endpoints of each edge of the degree of at least one less than2. The techniques of limited depth of the search tree is used to design the fixed parameters can solution algorithm. To undirected graph is preprocessed first, first of all the node in degrees greater than2marked with black spots, and then put the side mark on both ends is black spots as the black side, then the black border processing markers complex:the first step to deal with three connected directly without the black side of public endpoint, or deleted in the middle of the black side:Second step processing two black side directly connected, the randomly selected a black edge deletion; The third directly delete figure all the rest of the black edge. The time complexity of the algorithm is O*(2k).