ColloquiaTalk by Andras Farago on Friday, October 25

[Margery Ishmael]

-----------------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE

Friday, October 25th, 2002 at 2:30 p.m. in Ryerson 276

----------------------------------------------------------------------------------- 


Speaker: ANDRAS FARAGO, The University of Texas at Dallas

Title: On Algorithmic Challenges in Networking

Abstract:
Modern networking and telecommunications raise a number of
challenging problems. In certain cases these lead to algorithmic
models/problems that are interesting not only for the application, but
also in their own right, in a theoretical setting. The goal of this
presentation is to survey a selected set of such problems, with
special regard to open questions. As an example, a graph problem is
described below, motivated by network reliability issues in overlay
networks that are logical networks on top of a physical network. An
important practical issue in overlay network reliability is that the
failure of a single physical link can possibly disconnect a {\em set}
of logical links. This motivates the following family of problems.
Let G=(V,E) be a graph and let F={E_1,...,E_k}, E_i\subseteq E
be a family of edge sets in G. Let us call these "failure sets"
(each represents a potential failure). It is assumed that each edge
is contained in at least one failure set. For any edge set H let
F(H) be the minimum number of failure sets that cover H; we call this
the F-size of H. Task: find a cut with minimum E-size. That is, we
are interested in the minimum number of failure sets that can
disconnect the graph. Similarly, we can ask for a cut of minimum
F-size that separates two given vertices. If an oracle is given that
can decide for any two cuts S_1,S_2 in the input graph whether
F(S_1)< F(S_1) then we can prove the following positive results:
(1) If the size of the failure sets is bounded by a constant, then a cut 
with minimum F-size can be found in polynomial time.
(2) For arbitrary failure sets we can still do significantly
better than exhaustive search: a cut with minimum F-size can be found in
2^{O(\sqrt{am} \log m)} time in a graph with m edges and
k=O(m^a) failure sets.

Some open questions:
(1) Can the general case be solved in subexponential (i.e., 2^{O(m^{o(1)})} 
time, given an oracle that can compare the F-sizes of any two cuts in the 
input graph?
(2) Consider the paths between two vertices u,v. Two such paths are called 
F-disjoint if no failure set contains an edge from both, that is, a single 
failure E_i cannot disconnect both paths. Then a
natural question is to search for a maximum set of pairwise F-disjoint u-v 
paths. Is it possible to prove similar positive results for the maximum 
number of F-disjoint paths as for the minimum F-sized cuts or is the path 
problem fundamentally harder?

HOST: Laci Babai

*The talk will be followed by refreshments in Ryerson 255*