I have many different graph problems given. Such as finding an Eulerian circuit or finding a minimal spanning tree or a colouring of my graph.
Assuming, I have given a solution of a problem. Now, I want to verify this solution.
But can the solution of the problem be verified locally or do I have to look at the solution form a global point of view? For example: I want to verify a colouring of my graph. So, I can iterate over all my vertices and look at their neighbours. If the have different colours, my problem is locally solved. And if that’s the case for every vertex, I have a valid solution to my graph colouring problem.
But if I want to validate a Hamiltonian Circuit, simply checking for an incoming edge and an outgoing edge won’t do it.
So, I want to distinguish between problems that can be checked locally and such that can’t.
Is there a theory that deals with this kind of problem? I think I only lack the right technical term to find papers.
One way to phrase this is in term of reconstruction: what properties of a graph can be checked if you only have its subgraphs? There is a famous conjecture called the reconstruction conjecture which deals with the specific problem of checking a positive answer to the solution of the problem “is the graph isomorphic to the graph G?”.
– Mariano Suárez-Álvarez♦
2 days ago