1
$\begingroup$

Given an undirected graph $G$ of $N$ nodes and a starting node $s$, I want to build, with dynamic programming, a table whose $(k, n)$-th entry is $1$ if node $n$ is reachable with exactly $k$ steps from node $s$.

Specifically, for the first row of the table, I set $(1, n)$ to 1 if node $n$ is connected to node $s$. Then for the second row, I set $(2, n)$ to 1 if node $n$ is connected to any of the nodes who have value $1$ in the first row. I can stop the construction whenever I have a repeated row. In other words, I want to build the table to the point where more rows will be redundant, as there are already exact copies of them up in the table. So $k$ should be expressed in terms of $N$.

I want to check if this table construction can be done in polynomial time. I think it boils down to whether the number of rows is polynomially bounded. Is it so?

My intuition is yes, because in the worst case, where the $N$ nodes are serially connected one next to another, and starting node $s$ is at one end, I can still reach the other end with $N-1$ steps.

$\endgroup$
1
$\begingroup$

There is an easier way than dynamic programming. You can compute the adjacency matrix to the power of $k \in \mathbb{N}$. Let $m$ be your adjacency matrix. Then $m^k$ contains also paths of the length $k$. All other entries would be zero.

The runtime would be (because of only matrix multiplication): $\mathcal{O}(n^3)$

$\endgroup$
  • $\begingroup$ Wouldn't this be $O(k \cdot n^3)$, making it pseudo-polynomial? $\endgroup$ – ryan Jun 25 '17 at 22:42
  • $\begingroup$ I think it would be $\mathcal{O}(n^{3k})$ and then you are right: It would be pseudo-polynomial time. $\endgroup$ – Cilenco Jun 26 '17 at 7:34
0
$\begingroup$

Yes, your algorithm will run in polynomial time.

I'll offer a sketch of a proof. Let's assume for simplicity that your graph is connected; otherwise just take the connected component of your graph that contains node s. Now, let d be the maximum distance between s and any other node of the graph. There are two cases to consider: if the graph is bipartite or not.

If the graph is bipartite, then reaching a node in exactly k steps is equivalent to the node having a minimum distance of any number less than or equal to k but with the same parity modulo 2. Thus rows d and d+2 are the same, so the number of rows is bounded by V+1.

If not bipartite, then there must be an odd cycle. Consider a rooted spanning tree T of the graph, and call a node's depth its distance to the root. An odd cycle implies that there must be an outside connection between nodes of depth that are either both odd or both even in the spanning tree.

From now on we'll work in the subgraph that consists of T and this outside connection. Starting from any node x, after 50V steps, it's possible to reach every node that has depth the same parity as x. Therefore after 50V+2 steps, you can take the outside connection as a kind of "bridge," meaning that at least one vertex of opposite parity can be reached. Add another 50V steps and the entire graph can be reached, so the 100V+2 and 100V+3 step must both be identical (all 1's in the matrix).

EDIT: Just to clarify, 50 was an arbitrary number here. 2V or even V-(V%2) would also have sufficed.

Note that if you just wanted to build a table such that (k, n)-th entry is true if the minimum number of steps to reach n is k, then the algorithm you are looking for is Breadth-First Search, which is an optimal O(E) time.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.