The geocache is not at the posted coordinates. Solve the puzzle below to obtain the correct coordinates.
Graph theory is a field of mathematics that deals with the study of graphs, which are structures made up of vertices (also called nodes) connected by edges. One of the remarkable features of graph theory is its accessibility to amateurs, while at the same time offering deep insights to professionals.
A graph G is a pair (V, E), where V is a non-empty set of vertices (nodes) and E is a set of edges (links), and an incidence function ψ that associates with each edge of G an unordered pair of vertices of G. Below are some interesting graphs.
You do not need to know all of the intricacies of graph theory to solve this puzzle; you only need to know about dominating sets. A dominating set is a non-empty subset D⊆V(G) such that all vertices in V(G) are either in D or are adjacent to a vertex in D. In layman's terms, a dominating set is a collection of vertices in a graph that "touch" all vertices in that graph. For example, the vertices in red below are dominating sets.
A dominating set with the smallest possible number of vertices for a given graph is a minimum dominating set. The vertices in red above are all minimum dominating sets (check for yourself; see if you can find a dominating set that is smaller than the red vertices for each graph. Hint: you can't).
Your task is relatively simple: I will give you a graph, and you will find the minimum dominating set for that graph. You will then submit your solution through a checker, and it will return the coordinates if your minimum dominating set is 1) a dominating set and 2) minimum. The graph where you will find the minimum dominating set is below.
This graph has 1000 vertices and a lot of edges. Considering that the edges overlap into a nightmarish abyss, the adjacency list of the graph is provided for your convenience at this link. Each line represents a vertex and its connections. For example, line 0 = [11, 16, 18, 23, ...]. This implies that vertex 0 is adjacent to vertices 11, 16, 18, 23, and so on.
Before you start searching for the minimum dominating set, let's consider how long this task would take you if you systematically checked every possible combination of vertices. There are 2^1000 = 10^301 possible subsets of V(G). If every atom in the observable universe were a computer checking 1 trillion subsets per second, we would check about 10^92 subsets per second. As such, it would take around 10^301 divided by 10^92 = 10^209 seconds to guarantee a minimum dominating set. This is about 316, 887, 646, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000 years. You probably don't want to brute force a solution.
Your solution needs to be represented as a binary string. For example, the minimum dominating set for the following graph is 011001000011000, where each position in the string corresponds to a vertex in the graph. If you include a vertex in your dominating set, you should use a '1' in the corresponding position of the string. If you don't include a vertex, you should use a '0' instead.
To verify your solution, send an email with the subject: "GCA813G CHECK" and the body: "your solution" to this email (not listed in plaintext to prevent bot spam). For example, a submission for the graph above is below.
If your solution is both a dominating set and minimum, the checker will automatically email the coordinates to you. Otherwise, it should return an appropriate error message. If it doesn't reply after a minute, try sending your solution again. If it still doesn't reply, please contact me. Try your best not to spam the checker or send anything besides a binary string in the body; the checker likely won't break, but I also didn't try very hard to sanitize the inputs.
The checker runs a simple Python script that checks if your solution is a minimum dominating set for the provided graph; rather, it checks if your solution has at least as few vertices as the solution that I found. This problem is known to be NP-hard; it would still take longer than the length of the observable universe to guarantee that my solution is minimum. The solution that you are trying to beat is one that I calculated using a supercomputer. It is possible that you may find a better solution.