We first show the NP-completeness of Block Graph Deletion and Block Graph Editing by giving a reduction from Cluster Deletion and Cluster Editing, known to be NP-complete [1]}, [2]}, [3]}. Notice that Block Graph Completion admits
a polynomial-time algorithm due to the very nature of block graphs:
any biconnected component of the input graph (computable in linear time [4]}) must be turned into a clique.
