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.

Leave a Reply

4 Comments

  1. dhalps says:

    Easily shown via adversarial argument.

    • Agreed. Standard question (with no actual thought put into possible answers): what about restricted classes of graphs?

    • Alan says:

      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?

  2. jcmdev0 says:

    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.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>