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