Unconstraining
graph-constrainedgroup testing
Bruce Spang*, Mary Wootters
September 20, 2019

3. Unconstraining
2. graph-constrained
1. group testingGroup Testing
The setting is World War II…

🤠 🤠 🤠 🤠
🤠 🤠 🤠 🤢
Sick :(Group Testing🤠 🤠 🤠 🤠
💉🤠 🤠 🤠 🤢
Sick :(

Don’t need individual tests🤠 🤠 🤠 🤠

OkOk🤠 🤠 🤠 🤢
Sick :(We know this person is sickNeed to carefully design tests

Ok

Sick :(🤠 🤠 🤠 🤠
🤢 🤠 🤠 🤠

We can’t distinguish these twoOk

Need to carefully design tests

Ok

Sick :(🤠 🤠 🤠 🤠
🤠 🤢 🤠 🤠

We can’t distinguish these twoOk

Group Testing Problem
We have m items, at most d of which are defective.
Definition: A test returns whether a subset of items
includes any defectives or not.
Problem: Construct a set of tests which can identify any
set of at most d defective items.

Some known resultsO(d2 log m) easy construction

Include each person in a testwith probability 1/(d+1)Ω(d2 logd m) lower bound [Dyachkov-Rykov 82]
Random is pretty close to optimal

check citation style3. Unconstraining
2. graph-constrained
1. group testingA network

A network, failing🔥Finding failures🔥💌

Finding failures🔥💌

Graph-constrained Problem
We have a graph G=(V,E) with n nodes and m edges, at
most d edges are defective.
Definition: A graph-constrained test returns whether
any edges in a connected subset of edges are defectiveor not.
Problem: Construct a set of graph-constrained tests
which can identify any set of at most d defective edges.

Our informal result“You can do this nearly-optimally for lots of graphs(more than previously known)”

This seems surprising
For some graphs, these constraints matter a lotTheorem [Harvey et al 2007]: For the cycle graph on nnodes, at least n/2 tests required
Proof: Each neighboring pair of edges must be
separated by some test. Each test is a path and can only
separate two pairs. There are about n pairs.

Harvey et al 2007
Most general result: for any graph with more than dedge-disjoint spanning trees, can use O(d3 log m) tests
to identify at most d defective edges.

XHarvey et al 2007
Most general result: for any graph with more than dedge-disjoint spanning trees, can use O(d3 log m) tests
to identify at most d defective edges.

Cheraghchi et al 2010
• Current state of the art• Each test is a random walk on the graph
2d2 log m) tests!
Forcertaingraphs,candoitinO(τ•D-regular graphs, D ≥ 6d log2 nCheraghchi et al 2010
Good partsLimitations• Optimal for a complete graph!

• Degree requirement of log n means• Good expanders are nearly optimal:
oﬀ by O(log2 m)

it can’t deal with constant-degreeexpanders• Barbell feels like it should work but
doesn’t:n/2n/2

SummaryProblem: group testing, each test is connected subgraph
Lower bound: Ω(d2 logd m)
Gaps:• Constant mixing time: none2 m)Expanders:O(log•• Barbell: O(m)

3. Unconstraining
2. graph-constrained
1. group testingInformal result
If a graph suﬃciently well-enough connected, we canfind any set of d defective edges using O(d2 log m) tests
Same as unconstrained group testing

(β,α)-expanders
All sets S of size at most βn have a boundary of at least
α|S| edges

SV\S|S| ≤ βnat least α|S|edges

Examples of (β,α)-expanders
GraphβαEdge expander

1/2α

S|S| ≤ βnComplete

1/2V\Sn/2at least α|S|
edges

Barbell

1/4n/4

Main Theorem
Let G = (V,E), |V| = n, |E| = m be a (β,α)-expander, andd ≥ 0 whereα ≥ d/2 + O(1).
Then there exists a set of O(β-1d2 log m) tests that
identify any set of at most d defective edges.

Special Cases
Graph
CompleteD-regular expander
Erdös-Rényi Graph
G(n,D/n)Barbells

SourceNumber of Tests

At most d ≤ d0failures[CKMS10]O(d2log m)

d0 = Ω(m)Our workO(d2log m)

d0 = Ω(m)[HPW+07]O(d3log m)

d0 = Ω(D)[CKMS10]O(d2log3m)

d0 = Ω(D/log2m)

Our workO(d2log m)

d0 = Ω(D)[CKMS10]O(d2log3m)

d0 = Ω(D/log2m)

Our workO(d2log m)

d0 = Ω(D)[HPW+07]O(d3log m)

d0 = 1[CKMS10]O(m)d0 = m

Our workO(d2log m)

d0 = Ω(m)Algorithm108309413For 1…T:1112126• Include each edge with probability

75p ~ 1/d

• Use connected components larger
than βn2116182220192726231714152425

Proof outline• Recall from earlier, if we just pick edges withprobability ~1/d, we win if the resulting graph isconnected.

• If K ~ d log n, just pick each edge with probability ~1/d,the resulting graph is connected by [Karger 94]• We show most of the graph is connected when wepick each edge with probability ~1/d

Giant componentsModel: Fix a graph, keep each edge independently withprobability p.
Lots of previous work shows large connected components
exist above some value of p:101+ϵp=[Erdös-Rènyi59]•n1+ϵ• Expanders p = α

We show something stronger:• For each edge, the probability the edge is picked andincluded in a giant component is at least pε/8

830

94

131

112

12675

Open problems• Result for an arbitrary graph (start with a hypercube)• Find a deterministic algorithm

Thank you!

Technical Result
Let G=(V,E) be a (β,α)-expander, 0 < p < 1, G(p) be thesubgraph of G constructed by including each edge
independently with probability p, and C(u,v) be theconnected component of G(p) including edge (u,v).

1+ϵ,If p ≥αthen for all (u, v) ∈ Eℙ( | C(u, v) | ≥ βn) ≥ ϵ/2