Investigations Concerning Parameterized And Exact Algorithms For The Feedback Set And Related Problems

Feedback set and subset feedback set problems are two fundamental NP-complete graph problems in computer science.In various research fields such as bioinformatics,coding theory,and election theory,these problems play pivotal roles in essential mathematical models for addressing circular dependencies and conflicts in complex systems.The feedback set problem aims to find a set of vertices or edges of size at most6)in an9)-order graph,whose removal makes the graph without cycles.The subset feedback set problem,a generalization of the feedback set problem,further gives a subset of vertices or edges/arcs（called the terminal set）and aims to remove at most6)vertices or edges/arcs such that no terminal is contained in a cycle in the remaining graph.The development of social networks and artificial intelligence technologies highlights the importance of computing exact solutions with an acceptable exponential time complexity in the era of big data.This dissertation systematically investigates the computational complexity and explores parameterized and exact algorithms for feedback set and subset feedback set problems.It addresses the longstanding challenge of computational complexity classification and provides in-depth research on parameterized and exact algorithms for subset feedback vertex set problems（SFVS）in three important graph classes,all well-known implicit 3-hitting set problems.Whether 3-hitting set problems can be solved in O^*(2⁶))time is a famous open problem.This dissertation presents parameterized algorithms for these three implicit 3-hitting set problems breaking the crucial barrier 2⁶).Overall,this research achieves innovative theoretical results in the following four aspects.（1）Computational complexity classification of feedback set and related problems.This work addresses the long-standing challenge of classifying the computational complexity of feedback set problems in（planar）digraph graphs,particularly for graphs with maximum degrees of 3,4,and 5.Through the proposed concept of irregular planar embedding,we settle the classification of computational complexity regarding the maximum degree.Based on systematically organizing the reduction among various versions of subset feedback set problems,we also settle the classification of computational complexity regarding the size of the given terminal set.（2）Parameterized and exact algorithms for SFVS in tournaments.In addressing SFVS in tournaments,combining the sub-exponential time solution-separation technique,iterative compression,branching techniques based on blocks,and divide-and-conquer based on balanced cuts,this study improves the time complexity of parameterized algorithms from O^*(2.0755⁶))to O^*(1.6181⁶)),and for exact algorithms from O(1.5182⁹))to O(1.3820⁹)),respectively.These achievements not only provide the first parameterized algorithm breaking 2⁶)barrier but also match the running time bound of both parameterized and exact algorithms for the feedback vertex set problem in tournaments.Furthermore,this work significantly improves the parameterized and exact algorithms for the restricted version of SFVS in tournaments.（3）Parameterized and exact algorithms for SFVS in split graphs.This study designs a parameterized algorithm for SFVS in split graphs utilizing the Dulmage-Mendelsohn decomposition and branch-and-search technique.By employing the measure-and-conquer method,we prove that the parameterized algorithm runs in time O^*(1.8192⁶)),firstly breaking the 2⁶)barrier.Based on this algorithm,an exact algorithm running in time O(1.3488⁹))is additionally presented.Further expanding the scope of this work,an exact algorithm is established for the prize-collecting maximum independent set problem on hypergraphs,achieved by reducing it to SFVS in split graphs.This algorithm runs in O^*(1.8192⁹)),which is the first non-trivial exact algorithm that outperforms the brute-force approaches.Furthermore,based on dynamic programming and branch-and-search techniques,this work improves the parameterized and exact algorithms for the restricted version of SFVS in split graphs.（4）Parameterized and exact algorithms for SFVS in chordal graphs.This study innovatively proposes a novel divide-and-conquer approach based on tree decomposition,effectively linking SFVS in split and chordal graphs.This approach implies the faster parameterized and exact algorithms for SFVS in chordal graphs,improving the running time bound from O^*(2⁶))to O^*(1.6181⁶)),and from 1.5⁹)2^（9）)to O(1.3788⁹)),respectively.Notably,the time complexity of the parameterized algorithm first breaks the 2⁶)barrier.Furthermore,by employing a similar divide-and-conquer approach,this work improves parameterized and exact algorithms for the restricted version of SFVS in chordal graphs.