Some definitions:

Consider the unweighted directed graph $G$, where each node is uniquely represented by an $n$-bit vector of $0$'s and $1$'s.

Now consider this scenario: we want to 'shrink the dimension' of the index vectors for all nodes. For example, originally, some node has the index vector $\langle 0, 1, 1, 0 \rangle$ (so $n=4$), and we want to shrink the dimension to 2 by removing, for example, the first and third bit. Then the index for this node becomes $\langle x, 1, x, 0 \rangle$, where $x$ represents the removed bits.

$x$'s are considered the same bit. If in the original graph, the bitstrings differ only in these two bits, the two nodes will be merged as the same node after the 'shrinking'.

The edges are changed such that the new graph $G'$ contains an edge $(u,v)$ if and only if there were an nodes $u',v'$ 'shrunk' into $u,v$ such that $(u',v')$ is an edge in $G$.

My problem:

For a fixed source node $s$ and an arbitrary node $u$, we consider the shortest path between them: the distance of the node $u$ from $s$. Our objective is to minimized the longest such distance. Naturally, after the shrinking, the shortest paths can be different. Note that shrinkage can only decrease the objective value if not preserve the value as before shrinkage.

Now suppose we need to shrink $k$ bits out of the total $n$-bit vector and want to maximize the objective value from the source node in the new graph. How to decide which $k$ bits should we choose?

The decision version of the problem is

Given a graph $G = (V, E)$ as described above, a source node $s \in V$, an integer $k$ and an integer $C$, is there a 'shrinkage' of at most $k$ bits that creates a graph of objective value greater than $C$?

I have a feeling this is NP-hard, but failed to prove it by reducing it to some previous problems.

Any suggestions on the algorithms, reference literature, or refining my lousy descriptions are appreciated!

  • $\begingroup$ @D.W. I should have put the source node $s$ as an input. I also avoided the term diameter in the question. Thank your for your suggestions on clarifying my question:) Please let me know if it is still not clear enough. $\endgroup$ – linusz Apr 6 '17 at 0:22
  • $\begingroup$ The question can be reworded by using unit edge weights in G, and inserting zero-weight edges ("shortcuts") between nodes that would be folded together. What makes the process complex is that such a zero-weight edge may introduce paths that did not exist (at any cost) in the original G. $\endgroup$ – MSalters Apr 7 '17 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.