Open Problem: Graph traversal in small memory
We have a graph G and a pool of k locations. Each location can hold one node of the graph. We say that an edge is evaluated if both its endpoints reside in the pool. In order to evaluate all the edges of $G$, one has to take turns and move nodes in to the pool whenever needed. The cost of an evaluation is the total number of times nodes are loaded on to the pool. The problem is find an evaluation of minimum cost. Approximation algorithms are ok.
posted by metoo at 5:55 AM
9 Comments:
Do you know if this is NP hard?
What's the naive algorithm?
The memory isn't bounded by O(k) is it?
What is the application? a.k.a how did this problem come about?
I want a clarification - loading one node is one operation or if we load many node at a time in pool it's one operation.
ambiguous problem statement.
If I understood the problem correctly, then it seems to be NP-hard even for k=2, that is when only two vertices are allowed in the pool:
Let S be an optimal pool replacement strategie. We can assume that the strategie S adds each vertex only once to the pool. Moreover, we can assume that when a vertex v is added to the pool, either the other vertex currently contained in the pool is a neighbor of v or no neighbor of v has already been in the pool. Let then V' be the number of vertices that are contained in the pool for more than one turn. Observe that V' is a vertex cover of G. Let now G' be the subgraph induced by these vertices. Observe that each connected component in G' is a path, and that the number of pool replacements in S is exactly m+c, where c is the number of connected components in G. Let us therefore call a set of paths P a path vertex cover of G if and only if the vertices on the paths P form a vertex cover of G. Hence, we get the following optimization problem: given a graph G, find a path vertex cover of G of minimum size.
Observe that a vertex cover is a path vertex cover if we interpret each vertex in this cover as a path. Hence, the size of a minimum vertex cover is an upper bound on the size a minimum path vertex cover. On the other hand, if a hamiltonian path exists, then this hamiltonian path is clearly an optimal path vertex cover. The NP-hardness follows from this fact. Therefore, this problem is a mix of the hamiltonian path problem and the vertex cover problem. Approximation seems to be hard.
I have not found this problem in literature, but I have also not really searched for it.
To transfer the NP-hardness to bigger pools, simply "create" some vertices that need to be kept in the pool in an optimal solution. Specifically, if the pool has size k>2, then add k-2 vertices and connect these vertices with all other vertices. Clearly, an optimal solution should keep these vertices in the pool all the time. Anyway, it is quite unlikely that a bigger pool makes the problem easier. I guess that the approximation ratio grows with the size of the pool.
How is the case k=2 different to an Euler tour? Seems the |E| is an upper and lower bound for this case.
Graham
I am not 100% sure whether I understood the problem correclty.
The problem seems to the same as a pebble game that we studied in an earlier paper. I assume moving a single node into the pool contributes one to the cost.
Our paper and some prior work deal with the case of k=2. At first glance, the prblem may look the same as finding Euleran tours, but there is a subtle difference between the two.
Let k=2. Then the problem corresponds to finding the minimum travelling salesman tour with weights one and two on line graphs. Let me quickly mention the known combinatorial and computational results.
Combinatorial: Let G be any connected graph with m edges. Clearly, a minimum of m moves is needed. An upperbound of 1.25 m is known. This is tight; there exists a family of graphs relaizing this upperbound.
Computational: The problem is NP-Hard and MaxSNP-Hard even when the given graph is bipartite.
Referece: "On the complexity of join predicates", PODS 2001 and references given there.
We started working on the case of general k; we found it difficult and gave up.
Post a Comment
<< Home