# Set Inclusion

GIVEN: set of cards, some with blue backs, and each with a positive, integer face value.

QUESTION: Are there any [blue-backed cards] with a [face value <= L]?

- 2
**independent** variables: [blue/white cards], [integer face values]

**Function A**: Select a blue-backed card

- face value depends on which card you select
- each blue card
*potentially* has face value <= L
- thus, worst-case = [check all blue cards]

**Function B**: Select a face value <= L

- blue back depends on which card you select
- each card w/ face value <= L
*potentially* has blue back
- thus, worst-case = [check all cards w/ face value <= L]

Function B cannot exist. There is no way to verify that a selected card has a blue back, since don’t know key info:

- How are cards marked with a blue back?

WORST-CASE: turn over all blue-backed cards (Function A)

# Travelling Salesman

GIVEN: complete graph, G(V,E), where all edges are positive, integer values.

DEFINITION: “config”

- {A, B, u, v} where u & v are 2 vertices, and A & B are the remaining vertices split up as evenly as possible

DEFINITION: “optimal tour of a config”

- shortest path from u to v, only going thru each vertex in A once, and
- shortest path from v to u, only going thru each vertex in B once

Assume we have a function, `f`

, that returns the optimal tour for a given config, in constant time.

A smallest tour must be the optimal tour of one of the configs in G.

Any config could produce the smallest tour.

NOTE: Each tour is an edge-set that can form |V|/2 or |V| configs, for even or odd |V|, respectively.

A COMPLETE GRAPH is equivalent to: set of cards, some with blue backs, and each with a positive, integer face value.

- each
**card** represents a set of edges with size = |V|
**blue backs** mark any edge-sets that are an optimal tour for a config
**face value** is the sum of the edge-set represented by the card

QUESTION: Are there any [blue-backed cards] with a [face value <= L]?

- 2
**independent** variables: [blue/white cards], [integer face values]

Consider case where L = length of smallest tour.

- Only need look at blue cards (edge-sets that are an optimal tour for a config)
- Only need look at cards w/ face value = L (edge-sets with sum = L)

**Function A**: Select blue-backed card

- face value depends on which card you select
- each blue card
*potentially* has face value = L
- thus, worst-case = [check all blue cards]

**Function B**: Select a card with face value = L

- blue back depends on which card you select
- each card w/ face value = L
*potentially* has blue back
- thus, worst-case = [check all cards w/ face value = L]

Unlike “Set Inclusion”, now you can verify that a selected card for Function B has a blue back, by running `f`

on the selected card’s configs.

However, *controlling either variable, [choosing blue card] or [choosing card w/ face value = L], causes the other to be uncontrollable.*

WORST-CASE:

- FACE-DOWN Approach: turn over all cards with blue back (Function A)
- FACE-UP Approach: turn over all cards with face value = L (Function B)

So the final question: *Is TSP-Decision a version of “Set Inclusion” that has enough information to define a Function B*?

If so, does this mean that the worst-case running time of TSP-Decision is lower-bounded by the smaller of the 2 domains of Functions A and B? i.e. min{number of **blue cards**, number of **cards with face value = L**} — still only for the case where L = length of smallest tour.