Dirks, JonaGerhard, EnnaGesellschaft für Informatik e.V.2023-02-212023-02-212022978-3-88579-752-4https://dl.gi.de/handle/20.500.12116/40243The problem of packing modification-disjoint P₃ – an overview and an improved heuristic approach We consider the problem of packing modification-disjoint induced P₃. This has not been fully researched so far. Induced P₃ are especially relevant to solve the cluster editing problem. We provide an overview and new insights for locating modification-disjoint P₃ packing within the complexity hierarchy. Accordingly, we further look into conflict graphs. In response to our theoretical results, we create a significantly improved heuristic based on the approach of Spinner (2019). We then analyze its efficiency empirically on a selection of generated and public datasets. Our results show that it is either better than existing heuristics when comparing solution size and running time.enP3 PackingCluster EditingGraph TheoryHeuristicComplexity1614-3213