On the complexity of reconstructing H-free graphs from their star systems

Abstract

We prove that when H is a path or a cycle on at most 4 vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H-free Star System problem is NP-complete.

In particular, the problem is NP-complete when H is either a cycle or a path on at least 5 vertices.

Keywords

• complexity
• reconstructing
• H-free
• graphs
• their
• systems