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

January 19, 2022

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.


Profile picture

Written by Liu Yongliang who lives in Singapore. Also on Dev.to, LinkedIn, GitHub

© Copyright 2022 Liu Yongliang