Google Interview Question
SDE1sCountry: United States
for some *intuition* on why longest path is np-hard on a un-directed, general graph:
1. It's not a decision problem: if somebody would give you a longest path, you can't verify it in polynomial time, because in order to do so, you would need to know if there isn't an other, longer path. A strong argument it's not an NP-complete problem.
2. Why can't BFS / DFS solve the problem: Because the order in which you traverse the graph matters, by example:
(b)
/ \
(a)--(c)--(e)
\ /
(d)
let's assume some DFS traversals:
i) it did d->a->b->c->e it had it: is obviously a longest path
ii) d->a->c->e, a->b: isn't but one can argue, similar like the longest path in a DAG
works, one just needs to extend the existing DFS-tree when detecting a forward node,
so let's consider:
iii) d->c->b->a, c->e: maybe if we start from each node a dfs? e.g. from e) we must find
the longest path?
iv) e->c->d->a->b: cool, how about
v) e->c->a->d, a->b: hmm... maybe it aint that easy
3) you can derive the problem from the hamiltonian path, because if a hamiltonian path exists, that's the longest one. Deciding if a hamiltonian path exists in a graph is a well-known NP hard problem.
A simple BFS approach, considering with only 1 node. We can extend this to multiple nodes to check the longest paths. The neighbors are one direction mapped for simplicity-
public static void main(String[] args){
UndirectedGraphNode u0 = new UndirectedGraphNode(0);
UndirectedGraphNode u1 = new UndirectedGraphNode(1);
UndirectedGraphNode u2 = new UndirectedGraphNode(2);
UndirectedGraphNode u3 = new UndirectedGraphNode(3);
UndirectedGraphNode u4 = new UndirectedGraphNode(4);
UndirectedGraphNode u5 = new UndirectedGraphNode(5);
UndirectedGraphNode u6 = new UndirectedGraphNode(6);
UndirectedGraphNode u7 = new UndirectedGraphNode(7);
u0.neighbors.add(u6);
u0.neighbors.add(u4);
u0.neighbors.add(u5);
u0.neighbors.add(u1);
u1.neighbors.add(u3);
u3.neighbors.add(u2);
u2.neighbors.add(u7);
int max = Integer.MIN_VALUE;
int n = maxpath(u0, new ArrayList<>(), "", 0, max);
System.out.println(n);
}
public static int maxpath(UndirectedGraphNode graph, List<String> paths, String path, int len, int max){
if(graph == null)
return max;
List<UndirectedGraphNode> neighbors = graph.neighbors;
if(neighbors.size() > 0){
for(UndirectedGraphNode node: neighbors){
if(!paths.contains(path+node.label)){
if(node != null){
max = maxpath(node, paths, path+node.label, len+1, max);
}
}
}
}else{
paths.add(path);
max = Math.max(max, len);
return max;
}
return max;
}
static class UndirectedGraphNode {
int label;
List<UndirectedGraphNode> neighbors;
public UndirectedGraphNode(int x){
label = x;
neighbors = new ArrayList<UndirectedGraphNode>();
}
}
Assumptions:
- "unique path" means a path given by label is non-ambiguous
- longest path means the path that includes most labels / visits most vertices, without visiting vertices twice (hamiltonian path if exists is the best solution)
- as the name sais it's an un-directed graph, I assume, the given adjacency list rep. of
the graph ensures all eges (u,v) originating at u have an edge (v,u) originating
at v in it's "neighbors" list
- If I encounter a cycle, I do not consider infinte paths as a solution and try to find
the longest path that is not going through a cycle (I ignore the cycle)
- I rename "neighbors" to adjacents
The problem is NP hard. So, an exponential solution is okay. I am not sure, if there are approximation algorithms and how they look like.
Therefore, I'd completely forget about graph algorithms and do some sort of counting
using the adjacency list repr. of the graph:
- try all node's as first nodes
- now for the second node, try all adjacents of the first node, that aren't already used
- repeat until no more options are available, do this recursively, so all options are
evaluated. Stop if a hamiltonian path (all vertecis visted once) was accidentaly found.
- Chris November 07, 2017