An Algorithms Question
Define a “hub” to be a vertex that shares an edge with every other vertex (such as the middle of a star graph, or any vertex in a complete graph). Suppose we have the adjacency matrix of an undirected, unweighted graph with V vertices (so our input has size V^2). Find an algorithm with running time o(V^2) that can determine whether a hub exists in the graph, or prove that no such algorithm exists. Note the use of little-o notation: the algorithm must be asymptotically faster than (big) O(V^2).
My bet is that no such algorithm exists, but I can’t figure out how to prove it.
I’ll be at Mudd tomorrow, btw.
Easily shown via adversarial argument.
Agreed. Standard question (with no actual thought put into possible answers): what about restricted classes of graphs?
I agree that adversarial arguments are the way to go, but I can’t find a good one. If you look at the decision tree of the algorithm that supposedly can do this, it can check every edge somewhere in the tree, just not all of them in any given path through it. and I can’t prove that there exists a path through it that ignores an important edge.
…do you have a sketch of your easily shown proof?
If you had a list of degrees, you could probably do it in O(V), but determining the number of degrees would be O(V^2) if you didn’t have that.