{'fraction_non_alphanumeric': 0.054461181923522596, 'fraction_numerical': 0.0011587485515643105, 'mean_word_length': 4.503184713375796, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Complexity of Disjoint Π-Vertex Deletion for Disconnected Forbidden Subgraphs

We investigate the computational complexity of Disjoint Π-Vertex Deletion. Here, given an input graph G = (V,E) and a vertex set S ⊆ V, called a solution set, whose removal results in a graph satisfying a non-trivial, hereditary property Π, we are asked to find a solution set S′ with |S′| < |S| and S′ ∩ S = ∅. This problem is partially motivated by the “compression task” occurring in the iterative compression technique. The complexity of this problem has already been studied, with the restriction that Π is satisfied by a graph G iff Π is satisfied by each connected component of G [7]. In this work, we remove this restriction and show that, except for few cases which are polynomial-time solvable, almost all other cases of Disjoint Π-Vertex Deletion are \(\mathcal{NP}\)-hard.