[Cs5500] QUESTION REGARDING PROTOCOL FOR RL_BFS PLAYGROUND

[Karl Lieberherr]

Hi Sandeep:

see my earlier response with my answers to your questions below.

On Sun, Oct 2, 2011 at 3:34 PM, Sandeep Upendra Kamath
<kamath.s at husky.neu.edu> wrote:
> Dear Sir,
> When you introduced the RL_BFS playground in the class you suggested using
> "ForAllExists" protocol.
> But while discussing among ourselves we found this game not exactly
> following the above protocol.
> Heres our understanding of the game and it following  "ForAllExists"
> protocol:
>  -- ALICE :
> CLAIM: Alice makes a generic claim making a statement that  "n-node
> undirected graph G=(V,E)
> contains two nodes s and t such that the distance between s and t is
> strictly
> greater than n/2. And there exists some node v,not equal to either
> s or t, and deleting v from G destroys all s-t paths."
>  -- BOB: bob can do either of the following:
> (1) AGREES: if bob agrees (BOOLEAN = true),the agreement protocol is
> executed
> (2) REFUTES: if bob refutes the claim (BOOLEAN = false)then he provides an
> instance x= (G,s,t) for which he believes there is no "v".
>  -- ALICE:
> Alice now to defend herself solves the instance (G,s,t) by providing a "v"
> which on its removal disconnects "s" and "t".
> But our question about the above implementation is as follows
> (i) In the MMG domain cliam made was a value c, here the claim is just a
> generic statement. What would the propose function return.
You are right, in BFS the quality is constant 1. propose returns:
Claim =  <instanceSetWrapper> RWrap(InstanceSetI) <protocolWrapper>
RWrap(ProtocolI) <quality> double *s <confidence> double.

Let's use some nice syntax for
BFSInstanceSet = "(" "dist(s,t)>|V|/2" ")" implements InstanceSetI.

> (ii) How would the agreement protocol work in this case.

It should work as defined before (see slides from /lectures
directory): When Alice agrees with Bob on claim C:
defends(Alice,Bob,C) and defends(Bob,Alice,C) etc.

> (iii) We had a general question about the domain. Is claim  being made in
> this domain always true in the world of graphs.

Yes, it is true. Here is the proof: Construct the BFS search from
s to t by constructing the BFS layers and make sure distance(s,t)>|N|/2.
I claim that at least one of the layers must contain only one node
which is the node v we are looking for. Why?
> kindly guide us further.

Hope this helps. Above is the algorithm for the teaching avatar.

-- Karl

> Regards,
> Sandeep Kamath
> Team Navi
>
>
>