Insights into Advanced Algorithmic Problems
Talks on parts of 4 papers.
1)
M. Hajiaghayi, Khandekar and K.
2)
M. Cygan
,
K
3)
R Chitnis
,
M. Hajiaghayi
,
K
4)
M. Hajiaghayi, K and some students of M.
Hajiaghayi
The
3-SAT
problem with
n
variables and
m
clauses can not be solved in time
2
o(n)
Due to
Impagliazzo, Paturi and Zane
. FOCS
1998
. Do you think its false?
Lemma of
Calabro, Impagliazzo and Paturi:
The
3-SAT
problem with
n
variables and
m
clauses can not be solved in time
2
o(m)
This is called the
Sparsification Lemma
.
What can we prove under the
Exponential Time Hypothesis
?
Many problems have
“optimum”
running time algorithms under this
assumption.
We later present such a result in
connectivity. Tight lower bound that
uses the
Exponential Time Hypothesis
How can we prove that there is no
f(k)
poly(n)
algorithm for
Clique
?
The assumption of
P=NP
implies
that
f(k)
is polynomial in
n
.
To
show
Clique
FPT
we need to
show
P
NP
.
Instead: assume the much
stronger
ETH
assumption.
If you want approximation ratio of
for some problem what is the best
possible running time?
You need to do two things
First give an approximation ratio of
in some time
t(n)
.
Then show that approximation of
,
with time better than
t(n)
would
contradict the
ETH.
We start with this.
In
approximation algorithms
I do not think
somebody tried to show that in linear time
you can not get better than
2
ratio for
Vertex
Cover
. Should we create a new subject? If its
possible to prove such things.
Using the
ETH
this may be possible.
Needs knowledge far from
FPT
.
Needs a knowledge of almost linear
PCP
and
about
gap reductions
and about deep
theorems in
Inapproximability theory
.
See more later.
s
6
3
1
1
6
2
3
5
2
2
1
1
1
3
4
4
4
Optimum solution with all terminals
s
3
1
1
2
3
2
1
1
4
A very important problem in
Approximation
Algorithms
.
Key
for
other problems.
This problem is
FPT
by the
cost
of the
optimum solution.
It admits
n
for every
.
In the next slide I will give the
correct
credit for this result.
Never done
.
The best approximation algorithm for the
problem was designed in
SODA 1997
by
K,Peleg
. The credit
(by mistake)
is given to
Charikar et al
. Implies ratio
f(
)
n
for any
.
In
SODA 1998
Charikar et al used the same
algorithm. Said
explicitly
that Implies ratio
f(
)
n
for any
for the
Directed Steiner tree
.
Charikar et al
: better
f(
)
term.
Charikar et al
also implied that the problem
has
log
3
n
ratio, time
quasi-polynomial
in
n
.
At the time such an algorithm was considered
as a
sign
that a polynomial polylogarithmic
approximation exists.
A paper by
Chandra Chekuri and Martin Pal
:
under the
ETH, P
Quasi-P
Conjecture
(Kortsarz
):
Under the
ETH
there is
no polynomial time polylogarithmic ratio
approximation for the
Directed Steiner Tree
problem.
It turns out that linear reductions are crucial
for
Fixed Parameter Inapproximability
.
This is known for quite some time.
This means a reduction from
SAT
with
m
cluases and
n
variables that creates a gap.
The size of the instance of the new problem
is
O(m+n)
Unfortunately, if the
ETH
is correct there are
almost no linear reductions
.
Unfortunately
, a linear reduction from
PCP
to
Set-Cover
implies that
ETH
fails.
If we had that we could show that
Set-Cover
admits no
(r(k),t(k)) FPT
-approximation for
any
r,t
.
There is a linear reduction from
SAT
to
Clique
. This does not help because first we
need to do a
gap reduction
from
SAT
to
3-
SAT
.
SAT
with
n
variables and
m
clauses.
An almost linear reduction is
a reduction
to
Label-Cover
of size
m
1+o(1)
Known
(
Dinur
).
Reduction of size
m
polylog(m)
to
Label-Cover
,
gap
2.
The projection game conjecture
:
Moskowitz
:
Reduction to
Label-cover
of
size
m
2
log
1-
m
but gap
n
c
for some
c
.
W[1]-Hard
problem.
n
ratio approximation
This problem is clearly finding a
Directed Steiner
tree
and a
reverse directed Steiner tree.
The
Directed Steiner Tree
problem is
FPT
when
parameterized by the optimum solution
A rare case in which
FPT
time improves
drastically the approximation ratio.
As we saw, ratio
2
is possible in time
t(k)
poly(n)
.
Due to
Chitnis, Hajiaghayi, K
.
M. Cygan, K
If you want a ratio of
ln n/2
the time required is roughly
2
sqrt{n}
log n
Using the
ETH
we show that
this time is
optimal
(the
exponent can not be
o(sqrt{n})).
The upper bound is designing an
algorithm
.
The problematic part is the lower
bound. Relies on
Almost Linear
PCP
,
Projection Game conjecture
.
Different kind of knowledge.
Maybe because of that I found
very very few
results of this kind.
In this paper we define a
new way
to
use the known definition for
Fixed
Parameter Inapproximability.
We call this method
inapproximability
in opt
The definition requires
k=opt(I)
for
some
I
.
The definition was heavily influenced
by talks with
Cygan
and
Marx
.
Since approximation is in
opt
,
inapproximability
should also be in
opt
.
This is the
logical
counter
statement.
We were trying to avoid reduction
under
FPT
W[1]
,
FPT
W[2]
.
The
ETH
implies both statements
above.
Far reaching consequences.
ETH
implies
FPT
W[1],
FPT
W[2].
We are given that no time
t(k)
is
enough.
The value is usually
k
versus
k+1
for
minimization. Hard to get strong
hardness.
The proof above reduces
k
below any
given function. Thus
k
is not related
to any
opt(I)
.
However, if approximation in
opt
why not
inapproximabiliy in
opt
?
Also our definition does not throw all
problems in the same bin.
Does not seem logical that all prolems behave
the same. Completely different problems.
By our definition we get a
much richer
behavior.
Each problem,
its own behavior
.
Start with
SAT
. A
yes
instance
goes to value
X
for our problem.
A
no
instance goes to value larger
than
X
,
>1
for our problem.
Important: can produce
huge
gaps, solving the
k
versus
k+1
issue.
Polynomial algorithm with
ratio
implies
P=NP
A
approximation
algorithm with running time
2
o(m+n)
implies that the
ETH
fails.
A good
(
(opt), t(opt))
ratio needs
gap
preserving reduction that makes
opt
very small
. Not well understood.
We gave the first super exponential
time
inapproximability
for
Clique and
Set Cover
.
In fact for Clique Almost
doubly
exponential.
FPT
W[1], FPT
W[2]
does not imply
anything on the optimum solution of any
instance.
The problems are not thrown in the same bin.
In fact for every problem we check what kind
of
gap reduction
do we have?
For every problem: is there a gap preserving
(increasing, slightly decreasing) reduction
that makes
opt
very small
? The latter is the
new technical challenge.
It looks for simple variants of
Directed Steiner Network
that can
be solved exactly.
Its seem that there are not many.
The lower bounds do not use
almost linear PCP
but rather
something
standard
in
FPT
theory.
Let the vertices be
1,2,…..,n
Given
G(V,E)
and a demand
d
ij
for every
i
and
j
(could be
0
)
and cost
c(e)
for every
e
.
The goal is to select a subgraph
G(V,E’)
so
that there are
d
ij
edge disjoint paths from
i
to
j
(separately). Use minimum cost.
Hopeless problem to approximate.
For
Directed Steiner Forest
:
Feldman,K,Nutov
gave an
O(n
3/4
)
ratio.
But that is it.
What are the simplest solvable cases?
Given a graph
G(V,E)
with unit costs (makes a
difference!) and a root
s
output minimum
cost subgraph that contains
2
edge disjoint
paths from
s
to the other terminals.
Our usual trick (
Set Families
,
Uncrossable,
Weakly
Super Modular functions, Laminar
Basic Feasible solution
) do not work.
The idea of starting with
Directed Steiner tree
and then add edges to give two paths from
s
to all vertices seems to badly fail.
Given a
DIRECTED
graph
G(V,E)
and two
nodes
s
and
t
find a minimum cost graph so
that there is a path from
s
to
t
and from
t
to
s
The paths may not be edge disjoint.
Minimize the number of vertices in the
solution (reduction from the edge case).
We generalize this problem, and gave a tight
upper lower bound on the time.
Even the solution of the above non trivial.
Not shortest path.
We will have two tokes both in
s
.
One tokens,
f
goes on edges in the
regular
way
.
This creates the path from
s
to
t
.
A second token called
b
goes in the wrong
direction. This token would create a path
from
t
to
s
.
Bring the two tokens from
(s,s)
to
(t,t).
Due to
Jon Feldman
.
Token
f
moving forward
(u,x)
(v,x)
for an edge with
(u,v)
.
Token
b
moves backward (creating an
t
to
s
path):
(x,u)
(x,v)
for the edge
(v,u)
adding a back edge in the path
from
t
to
s
.
If both tokens reach
t
in the best way,
we solved the problem.
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
Edges
: (s,q), (q,p), (p,x), (x,t) (r,u) (r,y)
(u,t), (r,u), (y,r), (t,y) ,(p,x)
(s,s)
(s,u)
(q,u)
(p,u)
(p,r)
(x,r)
(t,r)
(t,y)
(t,t)
s
q
p
x
t
s
u
r
y
t
At the moment we enter a vertex, this
vertex is declared a
dead vertex
.
At every moment there must be a path
from the location of
f
to
t
using live
vertices.
And there must be a back path from
b
into
t
of live vertices.
The backward needs
x
. The forward needs
y
.
s
x
y
f
t
b
The following three paths must exist:
s
x
y
f
t
b
This contradicts
f
needing y to get to
t
.
s
x
y
f
t
b
We now move
(x,y)
to
(y,x).
Clearly a must.
s
x
y
f
t
b
We move from
(x,y)
to
(y,x)
but with one edge.
s
x
y
f
t
b
alive
alive
We make the graph with all pairs vertices
and edges as discussed.
We add edges from
(x,y)
to
(w,y)
with cost
c
: the cost of the shortest path
from
x
to
w
. Since direct edge move, dead
vertices
do not present a problem
.
We apply the
Dijkstra’s algorithm
to find the
shortest path on the graph of pairs, finding
the optimum
We have a structural lemma
Pity: even for
(2,2)
does not work (we give
an example that the structural lemma is
false)
We solve this generalization in time
n
O(k)
.
We show that under the
ETH
there is no
f(k)n
o(k)
Quite complex in my opinion. Uses the
grid
tiling
problem
.
Chen et al
showed a nice result about
k-clique
:
no exact solution in time
f(k)
n
o(k)
for any
f
.
Marx:
reduction from
k-clique to Grid
Tiling.
This reduction has surprising number
of applications.
Many in planar graphs.
We reduce from
Grid Tiling
to
our
problem with
linear blowup
The time lower bound follows.
This is also a
W[1]-hardness
reduction.
Are there other problems that use a
reduction from
Grid Tiling
for
W[1]
hardness?
Seems a complex reduction to me.
Do not prove
FPT
approximation unless the
problem is both
W[i]-hard
for
i≥1
and
has
poor approximation. If one of the two
statements is not true,
what is the point
?
Reductions should have only
super
exponential time
in
opt
(or
k
). Otherwise we
just translate a hardness to
FPT
terms.
Also, makes no sense to apply
FPT-
inapproximability
if the optimum is a
constant.
We feel that what we called
inapproximability in
opt
is the right
counter statement
to “approximation
in
opt
”. In our opinion “hardness in
opt
” is better.
Gives more
interesting
behavior.
Gives
large gaps/hardness
.
Needs knowledge in proving
hardness
of approximation
.
Given a problem,
FPT
people usually
know if it is
W[i]-hard
for
i≥1
.
But what about hardness?
Thus you have to either
know
the
approximation lower bound if exists,
or
prove
an inapproximability result.
There are
excellent books and lecture
notes
in
Approximation Algorithms
.
When you study a new problem, check if it
is in
FPT.
Or perhaps it is
W[i]-hard for i≥1
.
Fortunately: Nice slides by
Marx.
A new state of the art book by
Cygan et al.
People in approximation can make papers
on the topic of my talk:
“optimal”
time for
a required
approximation
.
Kernelization
,
Crown Reduction
,
Sunflower
,
Lemma
,
Bounded Tree search
,
Branching
Vectors
, all can give
FPT
algorithms for
Vertex cover
.
Forbidden subgraphs
(
Triangle Free Graphs
)
Iterative compression
(
Bipartite Deletion
)
Graph Minors (
k-leaves spanning tree
)
,
Color
Coding (
k length paths
)
,
Dynamic
Programming (
Steiner tree
)
,
Important
Separators
(
Multiway Cut)
,
Treewidth
………
Fellows
conjecture:
Clique
And
Set-Cover
admit no
(
(k),t(k))
approximation for any
,t
.
I believe this conjecture (even in
opt
).
May require a
Parameterized PCP
I talked to
Dinur, Khot
and other experts.
All told me in a very polite way:
Fellows
conjecture:
Clique
And
Set-Cover
admit no
(
(k),t(k))
approximation for any
,t
.
I believe this conjecture.
May require a
Parameterized PCP
I talked to Dinur, Khot and other experts.
All told me in a very polite way:
Please get
a hobby and leave us alone.
Fellows
conjecture:
Clique
And
Set-Cover
admit no
(
(k),t(k))
approximation for any
,t
.
I believe this conjecture.
May require a
Parameterized PCP
I talked to Dinur, Khot and other experts.
All told me in a very polite way:
Please get
a hobby and leave us alone.
However there is now a simple
PCP
and
simple
parallel repetition
theorems.
Say that
opt=logloglog n
. Is the
Set-Cover
and
Clique NPC
under this value?
What about if
opt=log* n
.
Better results: can we show an
inapproximability for
opt=log* n
.
According to the
Fellows conjecture
we
should not be able to give any approximation
thus the above value of
opt
do not matter.
Current
PCP
even the best possible (and not
known) gives double exponential time in
opt
lower bound.
How can we prove my conjecture?
No polynomial time polylogarithmic
ratio algorithm under ETH
.
The Directed Steiner tree has roughly
log
2
n lower bound.
Can we get exact
running times for
c log
2
n
approximations?
A
log
3
n
inapproximability I have no
idea how to prove.
Thank You
Delve into discussions surrounding complex algorithmic challenges, such as the limitations in solving the 3-SAT problem within specific time bounds, the Exponential Time Hypothesis, proving lower bounds for algorithms in various scenarios, and exploring approximation ratios in algorithm design. These insights touch upon crucial topics in computational complexity theory and highlight the interplay between theoretical assumptions and algorithmic performance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Talks on parts of 4 papers. 1) M. Hajiaghayi, Khandekar and K. 2) M. Cygan, K 3) R Chitnis, M. Hajiaghayi, K 4) M. Hajiaghayi, K and some students of M. Hajiaghayi
The 3-SAT problem with n variables and m clauses can not be solved in time 2o(n) Due to Impagliazzo, Paturi and Zane. FOCS 1998. Do you think its false? Lemma of Calabro, Impagliazzo and Paturi: The 3-SAT problem with n variables and m clauses can not be solved in time 2o(m) This is called the Sparsification Lemma.
What can we prove under the Exponential Time Hypothesis? Many problems have optimum running time algorithms under this assumption. We later present such a result in connectivity. Tight lower bound that uses the Exponential Time Hypothesis
How can we prove that there is no f(k) poly(n) algorithm for Clique? The assumption of P=NP implies that f(k) is polynomial in n. show Clique FPT we need to show P NP. Instead: assume the much stronger ETH assumption. To
If you want approximation ratio of for some problem what is the best possible running time? You need to do two things First give an approximation ratio of in some time t(n). Then show that approximation of , with time better than t(n) would contradict the ETH. We start with this.
In approximation algorithms I do not think somebody tried to show that in linear time you can not get better than 2 ratio for Vertex Cover. Should we create a new subject? If its possible to prove such things. Using the ETH this may be possible. Needs knowledge far from FPT. Needs a knowledge of almost linear PCP and about gap reductions and about deep theorems in Inapproximability theory. See more later.
s 6 3 1 1 2 1 1 4 6 3 1 3 2 4 5 4 2
Optimum solution with all terminals s 3 1 1 2 1 1 3 4 2
A very important problem in Approximation Algorithms. Key for other problems. This problem is FPT by the cost of the optimum solution. It admits n for every . In the next slide I will give the correct credit for this result. Never done.
The best approximation algorithm for the problem was designed in SODA 1997 by K,Peleg. The credit (by mistake) is given to Charikar et al. Implies ratio f( ) n for any . In SODA 1998 Charikar et al used the same algorithm. Said explicitly that Implies ratio f( ) n for any for the Directed Steiner tree. Charikar et al: better f( ) term. Charikar et al also implied that the problem has log3 n ratio, time quasi-polynomial in n.
At the time such an algorithm was considered as a sign that a polynomial polylogarithmic approximation exists. A paper by Chandra Chekuri and Martin Pal: under the ETH, P Quasi-P Conjecture (Kortsarz): Under the ETH there is no polynomial time polylogarithmic ratio approximation for the Directed Steiner Tree problem.
It turns out that linear reductions are crucial for Fixed Parameter Inapproximability. This is known for quite some time. This means a reduction from SAT with m cluases and n variables that creates a gap. The size of the instance of the new problem is O(m+n) Unfortunately, if the ETH is correct there are almost no linear reductions.
Unfortunately, a linear reduction from PCP to Set-Cover implies that ETH fails. If we had that we could show that Set-Cover admits no (r(k),t(k)) FPT-approximation for any r,t. There is a linear reduction from SAT to Clique. This does not help because first we need to do a gap reduction from SAT to 3- SAT.
SAT with n variables and m clauses. An almost linear reduction is a reduction to Label-Cover of size m1+o(1) Known (Dinur). Reduction of size m polylog(m) to Label-Cover, gap 2. The projection game conjecture: Moskowitz: Reduction to Label-cover of size m 2 log1- m but gap nc for some c.
W[1]-Hard problem. nratio approximation This problem is clearly finding a Directed Steiner tree and a reverse directed Steiner tree. The Directed Steiner Tree problem is FPT when parameterized by the optimum solution A rare case in which FPT time improves drastically the approximation ratio. As we saw, ratio 2 is possible in time t(k) poly(n). Due to Chitnis, Hajiaghayi, K.
M. Cygan, K If you want a ratio of ln n/2 the time required is roughly 2sqrt{n} log n Using the ETH we show that this time is optimal(the exponent can not be o(sqrt{n})).
The upper bound is designing an algorithm. The problematic part is the lower bound. Relies on Almost Linear PCP, Projection Game conjecture. Different kind of knowledge. Maybe because of that I found very very few results of this kind.
In this paper we define a new way to use the known definition for Fixed Parameter Inapproximability. We call this method inapproximability in opt The definition requires k=opt(I) for some I. The definition was heavily influenced by talks with Cygan and Marx.
Since approximation is in opt, inapproximability should also be in opt. This is the logical counter statement. We were trying to avoid reduction under FPT W[1], FPT W[2]. The ETH implies both statements above. Far reaching consequences.
ETH implies FPT W[1], FPT W[2]. We are given that no time t(k) is enough. The value is usually k versus k+1 for minimization. Hard to get strong hardness. The proof above reduces k below any given function. Thus k is not related to any opt(I).
However, if approximation in opt why not inapproximabiliy in opt? Also our definition does not throw all problems in the same bin. Does not seem logical that all prolems behave the same. Completely different problems. By our definition we get a much richer behavior. Each problem, its own behavior.
Start with SAT. A yes instance goes to value X for our problem. A no instance goes to value larger than X, >1 for our problem. Important: can produce huge gaps, solving the k versus k+1 issue.
Polynomial algorithm with ratio implies P=NP A approximation algorithm with running time 2o(m+n) implies that the ETH fails.
A good ((opt), t(opt)) ratio needs gap preserving reduction that makes opt very small. Not well understood. We gave the first super exponential time inapproximability for Clique and Set Cover. In fact for Clique Almost doubly exponential.
FPTW[1], FPT W[2] does not imply anything on the optimum solution of any instance. The problems are not thrown in the same bin. In fact for every problem we check what kind of gap reduction do we have? For every problem: is there a gap preserving (increasing, slightly decreasing) reduction that makes opt very small? The latter is the new technical challenge.
It looks for simple variants of Directed Steiner Network that can be solved exactly. Its seem that there are not many. The lower bounds do not use almost linear PCP but rather something standard in FPT theory.
Let the vertices be 1,2,..,n Given G(V,E) and a demand dij for every i and j (could be 0) and cost c(e) for every e. The goal is to select a subgraph G(V,E ) so that there are dij edge disjoint paths from i to j (separately). Use minimum cost. Hopeless problem to approximate. For Directed Steiner Forest: Feldman,K,Nutov gave an O(n3/4) ratio. But that is it. What are the simplest solvable cases?
Given a graph G(V,E) with unit costs (makes a difference!) and a root s output minimum cost subgraph that contains 2 edge disjoint paths from s to the other terminals. Our usual trick (Set Families, Uncrossable, Weakly Super Modular functions, Laminar Basic Feasible solution The idea of starting with and then add edges to give two paths from to all vertices seems to badly fail. Super Modular functions, Laminar Basic Feasible solution) do not work. The idea of starting with Directed Steiner tree and then add edges to give two paths from s s to all vertices seems to badly fail. ) do not work. Directed Steiner tree
Given a DIRECTED graph G(V,E) and two nodes s and t find a minimum cost graph so that there is a path from s to t and from t to s The paths may not be edge disjoint. Minimize the number of vertices in the solution (reduction from the edge case). We generalize this problem, and gave a tight upper lower bound on the time. Even the solution of the above non trivial.
We will have two tokes both in s. One tokens, f goes on edges in the regular way. This creates the path from s to t. A second token called b goes in the wrong direction. This token would create a path from t to s. Bring the two tokens from (s,s) to (t,t). Due to Jon Feldman.
Token f moving forward (u,x) (v,x) for an edge with (u,v). Token b moves backward (creating an t to s path): (x,u) (x,v) for the edge (v,u) adding a back edge in the path from t to s. If both tokens reach t in the best way, we solved the problem.
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) q p s x t (t,y) s u r y t
At the moment we enter a vertex, this vertex is declared a dead vertex. At every moment there must be a path from the location of f to t using live vertices. And there must be a back path from b into t of live vertices.
The backward needs x. The forward needs y. s f x b y t
The following three paths must exist: s f b x y t
This contradicts f needing y to get to t. s f b x y t
We now move (x,y) to (y,x). Clearly a must. s f b x y t
We move from (x,y) to (y,x) but with one edge. s b f x y alive alive t
We make the graph with all pairs vertices and edges as discussed. We add edges from (x,y) to (w,y) with cost c: the cost of the shortest path from x to w. Since direct edge move, dead vertices do not present a problem. We apply the Dijkstra s algorithm to find the shortest path on the graph of pairs, finding the optimum
