2
votes
0answers
126 views
If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well?
This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. No …
7
votes
1answer
587 views
Reconstruction conjecture: Can other decks do the job?
The standard reconstruction conjecture states that a graph is determined by its deck of vertex-deleted subgraphs.
Question: Have other decks been investigated, finding out
th …
