Skip to main content

Prove that the problem of determining whether a graph is connected is evasive

· 3 min read

P.S. My proof attempt/rewrite based on the solution discussed, uploaded mainly for my own reference. (warning: possibly erroneous)

Claim: The problem of determining whether a graph is connected is evasive​

  • evasive as in it requires n C 2 queries i.e checking all the edges
  • Prove by making an adversary argument
  1. Suppose M is an algorithm that makes m < (n C 2) queries to decide whether the graph is connected
  2. The adversary responds to each query as follows:
    • suppose it receives the x th query for 1 <= x <= m
    • it considers the graph x defined by taking
      • all the responses before this query (those that have reply of 1 => those edges that exist)
      • all unqueried edges are set to 1 and hence considered as exist
      • the current queried edge is set to 0 and hence not included
    • if this graph is still connected without the current edge, then the adversary replies 0, else replies 1
      • it's like if the graph does not need the current edge to be fully connected, then return 0
  3. After all m queries, there are
    • responses for previously queried edges, which can be 1 or 0
    • one unqueried edge that is unknown
  4. The adversary makes two graphs using the above information:
    • G0: take all edges that are connected according to the responses + set the unqueried edge to 0 (ignore the unknown edge)
    • G1: take all edges that are connected according to the responses + set the unqueried edge to 1 (include the unknown edge)
  5. M cannot distinguish between G0 and G1 because both are consistent with its queries.
  6. The argument is that G0 is disconnected while G1 is connected, and hence since M can only decide whether the graph is connected or not, M must be wrong for one of the above inputs.
  7. G1 is connected trivially because it is consistent with the adversary's response strategy.
    • If you set the unqueried edges to 1, then the graph must be connected (together with those edges that exist, i.e. previously answered 1)
  8. G0 is disconnected by contradiction:
    • Suppose G0 is connected for purpose of contradiction
    • Then let (i, j) = the last unqueried pair of nodes be connected, i.e there is a path between i and j
    • Given the adversary strategy, it must replied 1 to all edges on this path, because they exist
    • let (i', j') be the edge on this path that was queried last. Then the adversary should have answered 0 as i and j will be set as connected since they are unqueried at that point.
    • So a contradiction arises and the assumption is incorrect.

Concrete Example​

  • n = 3 example

  • Since the algorithm is going to decide whether the graph is connected or not, the adversary simply takes the input that is not consistent with the algorithm.