Optimal Parameterized Algorithms for Solving NP-Hard Problems in Topology

Abstract

Denne avhandlingen fokuserer på tre sentrale utfordringer innen algoritmisk topologi: homologibeliggenhetsproblemet, det minste omkransede kjedeproblemet og underflategjenkjenningsproblemet. Selv om disse problemene er ulike på mange måter, har de også noen fellestrekk: Hvert problem krever identifikasjon av en global understruktur i simplisielle komplekser, har både praktiske og teoretiske anvendelser, og er NP-komplette, noe som tyder på at de trolig ikke kan løses i polynomisk tid.

Hovedmålet med denne avhandlingen er å bruke parameterisert kompleksitetsteori til å utvikle praktiske algoritmer som kan håndtere disse utfordringene. Mer konkret har jeg fokusert på å utvikle fast-parameter-traktable (FPT) algoritmer som begrenser den forventede eksponensielle veksten i kjøretid til en eller flere parametere. På denne måten kan FPT-algoritmer håndtere NP-komplette problemer i praksis.

Denne avhandlingen utvider forståelsen av den beregningsmessige kompleksiteten til disse problemene under vanlige parameteriseringer, som løsningsstørrelse, koflategrad og trebredde. Viktige bidrag inkluderer utviklingen og implementeringen av flere nye FPT-algoritmer, etablering av negative resultater som W[1]-vanskelighet, XNLP-vanskelighet og presise nedre grenser basert på hypotesen om eksponentiell tidsbruk (ETH), samt utviklingen av en ny metode for å utlede ETH-baserte nedre grenser for algoritmer som er parameterisert av trebredde og stibredde av simplisielle komplekser.

This thesis examines three fundamental challenges in computational topology: the homology localization problem, the minimum bounded chain problem, and the subsurface recognition problem. Although distinct in nature, these problems share common features: each involves identifying a global substructure within simplicial complexes, offers both theoretical and practical applications, and is NP-hard, suggesting they cannot be solved in polynomial time.

The main goal of this thesis is to apply parameterized complexity theory to develop practical algorithms for these challenges. Specifically, I have focused on designing fixed-parameter tractable (FPT) algorithms that limit the exponential growth in runtime to the parameter alone, enabling NP-hard problems to be managed more effectively in practice.

This work enhances our understanding of the computational complexity of these problems under key parameters, such as solution size, coface degree, and treewidth. Contributions include inventing and implementing new FPT algorithms; establishing negative results, such as W[1]-hardness, XNLP-hardness, and tight lower bounds based on the exponential time hypothesis (ETH); and developing a novel approach to proving ETH-based lower bounds for algorithms parameterized by the treewidth and pathwidth of simplicial complexes.