  The celebrated Gibbard-Satterthwaite Theorem states that any surjective
social choice function which is defined over the universal domain of
preferences and is strategy-proof must be dictatorial. Aswal, Chatterji and Sen
generalize the Gibbard-Satterthwaite theorem by showing that the
Gibbard-Satterthwaite theorem still holds if the universal domain is replaced
with the linked domain. In this note, we show that determining whether an
election is linked can be done in polynomial time.
