A Study On FPT Algorithm Based On Hidden Structure In Graph Class Problems

The purpose of graph modification is to make a given graph have certain properties through graph modification operations.Generally speaking,graph modification operations mainly include edge deletion,addition,and vertex deletion.This problem is a classic type of NP-hard problem,which has applications in many fields in real life and has become a research hotspot of scholars in recent years.Parameterized computation and complexity theory is a new method for experts and scholars to deal with NP-hard problems.Using this theory,new algorithm design and analysis techniques and problem models can be applied to computational problems in many fields.In this paper,the problem of unit interval edge deletion and line edge deletion are studied from two aspects of fixed parameter tractable algorithm and time complexity analysis of the algorithm.The specific research results mainly include the following points:The proper interval edge deletion problem has been proved to be an NP-hard problem,and there are a lot of studies in different literatures.First,the researcher fully considered the structural relationship between the maximum forbidden subgraph and other forbidden subgraphs,and proposed a parameterized algorithm with a time complexity of O*(6k)for this problem.Then someone proposed an algorithm with a time complexity of O*(4k)on this basis.An important observation used in this algorithm is that after deleting some edges in the net or tent,some new prohibition-induced subgraphs will be generated,triggering further deletion of edges.In this paper,by analyzing the hidden structure of C4,the time complexity of the algorithm is improved to O*(3.792k).The line edge deletion problem is to decide whether the graph G can be transformed into a line graph by deleting at most k edges,given a simple undirected graph G and a parameter k.At present,some researchers rely on the structural characteristics of the line graph to design a kernelization algorithm with a kernel size of O(k5)for the edge deletion problem of the line graph.And this paper proposes a fixed parameter tractable algorithm for line graph edge deletion problem based on the prohibition-induced subgraph structure of the line graph.The paper applies the algorithm idea of the unit interval edge deletion problem to this problem,and analyzes in detail the situation of one of the prohibition to induce all possible neighbors of the subgraph.Finally,through the analysis,the algorithm time complexity is O*(8.02k).The research results on branch search technology in this paper provide a reference for solving graph problems based on implicit structure,and provide a new idea for designing parameter algorithms for other NP-hard problems,which enriches and develops branch search technology to a certain extent.