Solution to The Scorpion Problem

The Problem:

A scorpion on n vertices is a graph that has a vertex of degree 1 (the tail), connected to a vertex of degree 2 (the body), connected to a vertex of degree n-2 (the head). The other n-3 vertices (the feet) can be arbitrarily interconnected.

Give an O(n) algorithm for deciding whether or not an arbitrary graph is a scorpion, assuming that the graph is represented by an adjacency matrix.

The Solution:

Motivation:

If a graph is a scorpion, it must have a tail, a body and a head. If a graph contains no potential head and tail, it could not be a scorpion. If it contains a potential head and/or a potential tail, verifying if it is a scorpion can be done in linear time. So, the key point in this solution is to find out the potential head and tail in linear time.

Definition: For any vertex v in G

1. adj_v: {i | A(i,v)=1};
   
2. nonadj_v: {i | A(i,v)=0, i != v}.
   

Algorithm:

• Input: An n*n adjacency matrix A of graph G;
  
• Output: True if G is a scorpion; False if G is NOT a scorpion.
  
  
• If n<4, by definition G can NOT be a scorpion. Output FALSE and exit.
  
  
• If n=4, compute adj_i, i=1,2,3,4. Sort | adj_i |, if the quadruple (| adj_1 |,..,| adj_4 |)= (1,1,2,2), then output TRUE. Otherwise output FALSE. Where the operator "|" means calculating the cardinality.
  
  
• If n >= 5, Take any vertex v, where v is in [1..n]. Compute adj_v and nonadj_v.
  
  
• CASE 1: If | adj_v | = 0, then the degree of v is 0, G is NOT a scorpion, output FALSE, as a scorpion doesn't have a vertex with degree 0.
  
  
• CASE 2: If |adj_v|=1, suppose adj_v={k}, compute adj_k and nonadj_k.
  
  
  1. CASE 2a: if |adj_k|=2, suppose B1={w,v}, compute adj_w. If |adj_w|=n-2, then ouput TRUE. Otherwise output FALSE.
     
     
  2. CASE 2b: if |adj_k|=n-2, then |nonadj_k|=1. Suppose nonadj_k={y}, compute adj_y. If |adj_y| is NOT equal to 1, then output FALSE. Otherwise, |adj_y|=1, suppose adj_y={z}, compute adj_z. If |adj_z|=2, then output TRUE. Otherwise output FALSE.
     
     
  3. CASE 2c: if |adj_k| is equal to the others, then ouput FALSE.
     
     
• CASE 3: if |adj_v|=2, suppose adj_v={a,b}, compute adj_a, nonadj_a and adj_b, nonadj_b. If there is ONLY one adj_x, x=a or b, such that |adj_x|=n-2, then do the same job as CASE 2b only changing k to x. Otherwise ouput FALSE.
  
  
• CASE 4: if |adj_v|=n-2, then do the same job as CASE 2b only changing k to v.
  
  
• CASE 5: if 2 < |adj_v| < n-2, then 2 < |nonadj_v| < n-2. Let d=|adj_v|, we have |nonadj_v|=n-1-d. Do the following program:

         while !(|adj_v|==0 or |nonadj_v|==0) do
            {
             k = the first one of adj_v;
             j = the first one of nonadj_v;
             if (A(k,j)==1) then
                 delete j from nonadj_v;
             else
                 delete k from adj_v;
            };
  
         if (|nonadj_v|==0) then
            {
             output FALSE;
             exit;
            }
  
         if (|adj_j|!=1) then
            {
             output FALSE;
             exit;
            }
         else
            {
             do the same job as CASE 2 by replacing v to j;
            }
  

Proof of correctness:

To check whether a graph G is scorpion, we need first confirm the head as ONLY head has degree n-2 in a scorpion. If we find a vertex v with degree n-2, then as there is ONLY one vertex w not adjacent to v, if G is a scorpion, the degree of w must be 1 and the degree of vertex y adjacent to w must be 2. Reversely, if the degree of w is 1 and the degree of vertex y adjacent to w is 2, as degree of v is n-2, y is adjacent to v and the left vertices. Also no left vertices are adjacent to w and y due to the degrees of w and y. So G is a scorpion. So once we find a vertex v with degree n-2, we can check whether G is a scorpion.

In our algorithm, we first choose any vertex v in the graph G and compute adj_v and nonadj_v.

If |adj_v|=0, G is disconnect and can NOT be a scorpion.

If |adj_v|=1, v may be either a foot or a tail. Then we check the degree of the vertex k adjacent to v. If v is a foot, degree of k is n-2. If v is a tail, degree of k is 2. Otherwise G can NOT be a scorpion. So we think only the two cases. If degree of k is n-2, then as we prove above, we can determine whether G is a scorpion. If degree of k is 2, then the degree of vertex w adjacent to k but differnet from v is n-2, iff G is scorpion by the definition of scorpion. By check |adj_w|, we can still check G in this case.

If |adj_v|=2, v may be either a foot or a body. If G is a scorpion, in each case, there is one and only one vertex with degree n-2 which is adjacent to v. Once we find such vertex, we still can check whether G is a scorpion by proof before.

If |adj_v|=n-2, as proof before, we can check G.

If 2 < |adj_v| < n-2, then v must be a foot, if G is a scorpion. So the tail and body are not adjacent to v and in nonadj_v, the head is adjacent to v and in adj_v. Since tail is adjacent only to body, it is not adjacent to any vertex in adj_v. So by our algorithm, the tail can NOT be deleted and will delete all the vertices in adj_v and only it can as head is in adj_v. So if nonadj_v become empty, G is not a scorpion. If adj_v becomes empty, we need only check whether the one in nonadj_v which deletes all vertices in adj_v is a tail, just following case 2 we can have it done.

So for any case, we can check whether G is a scorpion.

Complexity:

For any vertex v, computing adj_v and nonadj_v needs O(n) time. For case 1-4, each case at most compute some adj_x and nonadj_x 4 times and some constant comparision. So the total running time for each case in case 1-4 is O(n).

For case 5, the total number of adj_v and nonadj_v is n-1, at each inner loop, one vertex must be deleted from adj_v or nonadj_v. So the running time of the whole loop is at most O(n). So the running time of case 5 is O(n)+running time of case 2. It is still O(n).

So the running time of the whole algorithm is O(n).

Solution by: Wenqing Deng, Yangang Li, Anuradha Sethuraman , Jun Wang.