Détail du document
Identifiant
oai:arXiv.org:2410.23878
Sujet
Computer Science - Data Structures... Computer Science - Discrete Mathem...Auteur
Berthe, Gaétan Bougeret, Marin Gonçalves, Daniel Raymond, Jean-FlorentCatégorie
Computer Science
Année
2024
Date de référencement
06/11/2024
Mots clés
graphsRésumé
In this paper, we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cycle-hitting problems: Feedback Vertex Set (FVS) and Triangle Hitting (TH).
We focus on the class of pseudo-disk graphs, which forms a common generalization of several graph classes where such results exist, like disk graphs and square graphs.
In these graphs, we show that TH can be solved in time $2^{O(k^{3/4}\log k)}n^{O(1)}$, and given a geometric representation FVS can be solved in time $2^{O(k^{6/7}\log k)}n^{O(1)}$.
;Comment: Presented at the conference WG 2024
Berthe, Gaétan,Bougeret, Marin,Gonçalves, Daniel,Raymond, Jean-Florent, 2024, Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
Optimal Sensing of Momentum Kicks with a Feedback-Controlled Nanomechanical Resonator
sensing momentum kicks resonator
Shared genetic aetiology of Alzheimer’s disease and age-related macular degeneration by APOC1 and APOE genes
gene diagnostic based analysis amd ad apoe apoc1 identified genes pleiotropy
