An $$O^{*}(1.4366^n)$$-time exact algorithm for maximum $$P_2$$P2-packing in cubic graphs

Given a graph \(G=(V, E)\), a \(P_2\)-packing \(\mathcal {P}\) is a collection of vertex disjoint copies of \(P_2\)s in \(G\) where a \(P_2\) is a simple path with three vertices and two edges. The Maximum \(P_2\)-Packing problem is to find a \(P_2\)-packing \(\mathcal {P}\) in the input graph \(G\) of maximum cardinality. This problem is NP-hard for cubic graphs. In this paper, we give a branch-and-reduce algorithm for the Maximum \(P_2\)-Packing problem in cubic graphs. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time \(O^{*}(1.4366^n)\) which is faster than previous known exact algorithms where \(n\) is the number of vertices in the input graph.