lundi 26 juillet 2021

relaxed version of feedback vertex set (FPT)(sampling algorithm)

problem: for a given undirected graph G and k ∈ N, and the objective is to decide whether there exists a subset X ⊆ V (G) of size at most k such that every connected component in G − X is either a tree or a cycle.

we need to design a 4^k * n^O(1) running time FPT algorithm

My motivation is to use a sampling algorithm, but for that, the graph should be with a minimum degree of 3. I wrote a reduction rule for all vertex with degree 0, but I struggle to write reduction rules for degrees 1 and degrees 2 without increasing parameter k.




Aucun commentaire:

Enregistrer un commentaire