Checking graph properties in linear time given only the adjacency matrix

2
votes

I came across a problem concerning graphs. Let's define a rake graph.

A n-vertex graph is a rake when it meets certain conditions:

  1. there is a vertex of degree 1 in the graph
  2. this vertex is connected to a vertex of degree 2
  3. this second vertex is connected to another vertex of degree n-2 other vertices may or may not be connected to each other.

I have been given an adjacency matrix for a graph of n vertices. My task is to check if the graph represented by the given matrix is a "rake" or not. The catch is that is has to be done in linear time.

I've tried like everything. It's easy to do when you have adjacency list, but how do I make it take O(n) time with the matrix given?

1
algorithmgraphadjacency-matrix
Simply scan adjacencies accumulating counts for each node as you go using a hashtable to hold the counters for each node. Then check the nodes to see if there is one of adjacency 1,2, and n-2. That's O(n). – RBarryYoung
@RBarryYoung could you say a bit more? I think this problem is not trivial (at least for my skill set). – artur grzesiak
just to be 100% clear about O(n) for the worst-case? (btw. it is really nice problem;-) thanks for that! ) – artur grzesiak
well, this problem is said to have a linear solution in all the cases. The only hint I have is that "from the point of being a rake, the vast majority of vertices is not important" - obviously meaning the last vertices coming from the centre – Simon
:-) it is not important but still they are there! – artur grzesiak

1 Answers

1
votes

Okay I seem to have found an answer! There indeed is a linear time algorithm solving this problem, because the problem I presented is called in the world of science checking if a graph is a scorpion graph!

Here you can find the algorithm I'd been looking for. http://www.cs.cornell.edu/courses/cs681/2007fa/Handouts/scorpion.pdf

Thanks for help!