Click this Icon for an Abstract.
Or click here to show all abstracts.

Journal articles based on a (single) refereed conference version, are merged,
and sorted based on the date of the more recent (journal) publication.
This is a Google-scholar profile for the purpose of citations (as my name appears in various forms on papers).

We want to build a network that can transport any demand matrix $\left({D}_{ij}\right)$ where
$\sum _{j}{D}_{ij}\le {b}_{i}$. The $b}_{i$'s are called marginals - they simply indicate that the
total demand (traffic) involving node $i$ is at most $b}_{i$. The class of all
such matrices are called the hose matrices. We dont know or care who $i$ will actually
communicate with. In addition, we must route traffic "obliviously", which means that routing of traffic between
nodes $i$ and $j$
does not depend on what other traffic there is in the network. In other
words, our routing cannot
adapt to congestion in the network: we must prespecify how any pair
communicates regardless of which hose demand matrix
we are given. Our goal is to find an oblivious routing such that the
total capacity needed on the edges of the network
is minimized. This is called the Virtual Private Network (VPN) problem.
Fingerhut-Suri-Turner and Gupta-Kleinberg-Kumar-Rastogi-Yener
showed that there is always a tree network whose total
cost is within a factor of 2 of the minimum cost VPN. It was widely
speculated and conjectured in Italiano-Leonardi-Oriolo,
that there is always an optimal VPN which is a tree. We show this is
true using pyramidal routing, a concept recently introduced by
Grandoni-Kaibel-Oriolo-Skutella to attack the VPN problem.

The maximum edge-disjoint path problem (EDP) consist of a supply graph and some
terminal pairs $s}_{i},{t}_{i$ for $i=1,2...,k$. The goal is to find a maximum subset of the
pairs that can be simultaneously satisfied by disjoint paths in the supply graph.
Guruswami et al. (see below) showed that in directed graphs the maximum edge-disjoint path problem (EDP) is hard to
polytime approximate to better than a factor of $m}^{.5-\epsilon$ (where m is the number
arcs and any $\epsilon >0$). However similar hardness results were not known for the undirected version
(it was only known to be hard to constant approximate).
This paper studies a relaxation of EDP in undirected graphs, the all-or-nothing multicommodity flow problem,
where one is only asked to find a subset of the pairs for which there is a flow satisfying their demands.
The main result is that the integrality gap for this relaxation is
at most a polylogarithmic factor (thus exponentially
better than for directed graphs). Recently an almost matching polylogarithmic lower bound
was found by Andrews and Zhang.

We design a game-theoretic framework to analyze contracts between competing parties on the Internet, partly inspired
by issues arising in interdomain routing.

We show for the first time a class of (separable) demand polytopes for
which the associated robust network design problem exhibits polylog
hardness.
We also show that for the class of demand polytopes induced by a tree
(T-topes) there is an 8-approximate polytime algorithm
(though this class of problems may possibly be in P).

Consider the robust network design problem of finding a minimum cost
network with enough capacity to route all traffic demand matrices in a
given polytope.
We investigate the impact of different routing models in this robust
setting: in particular, we compare \emph{oblivious} routing, where the
routing between each terminal pair must be fixed in advance,
to \emph{dynamic} routing, where routings may depend arbitrarily on the
current demand.
Our main result is a construction that shows that the optimal cost of
such a network
based on oblivious routing (fractional or integral) may be a factor
of $Big\Omega \left(log\phantom{\rule{0ex}{0ex}}\left\{n\right\}\right)$ more than the cost required when using
dynamic routing. This is true even in the important special case of
the asymmetric hose model. This answers a question in
\cite{chekurisurvey07}, and is tight up to constant factors. Our
proof technique builds on a connection between expander graphs and
robust design for single-sink traffic patterns~\cite{ChekuriHardness07}.

In recent years, several new models for network flows have been
analyzed, inspired by emerging telecommunication technologies.
These include models of {\em resilient flow}, motivated by the
introduction of high capacity optical links, {\em coloured flow},
motivated by Wavelength-Division-Multiplexed optical networks, {\em
unsplittable flow} motivated by SONET networks, and {\em confluent
flow} motivated by next-hop routing in internet protocol (IP)
networks. In each model, the introduction of new side-constraints
means that a max-flow min-cut theorem does not necessarily hold,
even in the setting where all demands are destined to a common node
(sink) in the network. In such cases, one may seek bounds on the
$}$flow-cut gap'' for the model. Such approximate max-flow min-cut
theorems are a useful measure for bounding the impact of new
technology on congestion in networks whose traffic flows obey these
side constraints.

For planar graphs, we show that if each edge capacity
is at least 4, then the natural LP for the maximum
integral multicommodity flow problem has a constant integrality gap
(as opposed to $\sqrt{n}$ if capacities are at most $1$).

We consider the single sink multicommodity flow problem where
flow out of any node may use at most $d$ arcs. If $d=1$, then such flows
are called confluent; if $d=2$ we call such flows bifurcated. It was previously
shown that confluent flows may have node congestion up to $O\left(log\phantom{\rule{0ex}{0ex}}\left(n\right)\right)$.
We show that for $d=2$, this unbounded congestion gap disappears: we show that
the congestion gap is at most 2 (and this is best possible).
In order to better understand the trade-off between $d=1$ and $d=2$, we consider
the $\beta$-confluent flow problem for $\beta \in [0,1]$. Here we require
that a $\beta$ fraction of the flow out of any node must exit on a single arc
(and the remainder on possibly one other arc). We show that for any $\beta \in [\frac{1}{2},1)$,
there is a $\beta$-confluent flow of congestion at most $(1+\frac{\beta}{1-\beta})$.

We study problems related to the design of transparent optical networks, where
flow paths must also be assigned an $}$end to end'' wavelength (colour). If,
this is impossible, an expensive (OEO) conversion takes place. We try to partition the edges of a graph
into transparent islands so that no demand has to hop between islands too often. In a different
version, we show a simple fractional implies integral result for single source multicommodity
multicoloured flow.
This reduces the corresponding WDM network design problem
to a single-source buy at bulk problem with single cable type, for which
a 3.55 approximation is known (Hassin, Ravi, Salman).

We introduce a noncooperative game in an effort to understand business relationships
between entities (enterprises, ISPs, residential customers etc.) on the Internet.
Contracts are local (ie bilateral) between two entities and
may either be of a peer-to-peer or a customer-provider variety.
Entities bid (or demand payment) for the formation of these contracts,
and in the resulting network some traffic is routed and other traffic dropped;
providers may incur a penalty if their customer's traffic is dropped.
Stable solutions to this game may have some interesting properties, including
lending of money with long-range effects (money trickles into the hands of distant entities
having nothing to do with the customer who paid).

We are given an uncapacitated undirected graph $G$ and a collection $P$ of
matrices for pairwise traffic demands between nodes of $G$.
What is the cheapest assignment of edge capacity needed so that any matrix $D$
in $P$ can be routed using this capacity? In the "oblivious routing" setting,
for each pair $i,j$ there is a pre-specified unit flow ("template") and one may only
scale this flow up or down according to the value of $D}_{ij$. In this version
Applegate and Cohen showed that the optimal capacity is computable in polytime.
If we may choose our flows dynamically for each different demand matrix, then obviously
we may need less capacity. We show, by a reduction from graph expansion, that this problem
is hard, even for a single-source hose problem (and even to get within a factor 2).

Garg, Vazarani and Yannakakis showed examples where the integrality gap
(the natural formulation) for the maximum edge disjoint path problem (EDP) is
as bad as $\sqrt{n}$ even for planar graphs. For planar graphs, we show that if each edge capacity
is at least 2, then this integrality gap drops to log(n).

We introduce the following problem.
Given a graph $G$ where each node $v$ has a capacity $b\left(v\right)$,
and we are also given a set of edges $F$ where each such $f\in F$
also comes with an integer demand $d\left(f\right)$ and weight $w\left(f\right)$. A subset $M$ of $F$
is a *demand matching* if for each node, the total demand of $M$-edges incident to
it is at most $b\left(v\right)$. We study the natural IP formulation for this (NP hard) problem and find that
its integrality gap lies between 2.5 and 3 for bipartite graphs, and between 3 and 3.5 for general graphs.

Network design problems arising from supermodular set requirement functions
have been well studied, as have orientation problems where one wishes to orient
some undirected edges to satisfy some connectivity conditions. Motivated by the design
of strongly connected networks,
we consider (for the first time as far as we know) the problem of joint orientation and
subset selection of edges/arcs.
The main finding is that a classical result of Frank on intersecting supermodular
functions extends very simply to the joint setting.

Decompositions are described for visualizing when a set of arcs forms a dijoin.
An elementary algorithm is given for finding a mincost dijoin that runs in O(n^2m) -
matching the best running time due to Gabow. A number of questions are posed related to packing
dijoins. One of these is that there exists a constant $C$ such that in any weighted digraph
whose minimum weight directed cut is of size $k$, there is a packing of $Ck$ dijoins (into the weights).
It is proved there is a half-integral such packing.

We consider the multicommodity *all-or-nothing flow problem* in a tree.
We are given a tree with integer edge capacities
$u\left(e\right)$ and a set $F$ of demand edges $f=uv$, each with an integer $d\left(f\right)$.
A subset of demands is *routable* if no edge capacity is violated after each demand sends $d\left(f\right)$ units of flow
between its endpoints. Special cases of this problem include when the tree is a single edge
(knapsack problem), when the tree is a star (demand matching problem) and when all demands
are 1 (integer multicommodity flow on a tree), or when the tree is a line (interval packing),
and when the tree is a star (the b-matching problem).
For the unit demand case, Garg, Vazarani and Yannakis gave a 2-approximation for the
the maximum cardinality problem. We show that the integrality gap for the weighted (unit demand)
case is at most 4. Following, Cheriyan, Jordan, and Ravi, we ask whether this can be brought down
to 3/2 (thus generalizing Shannon's multigraph edge colouring result).
Our result together with a technique of Kolliopoulos and Stein can then be used to
show that for general demands, a gap of at most 48 holds (the first constant factor for this problem).

The main new result in this paper is a
**polytime algorithm ** to determine whether a graph is partitionable:
i.e., for each node v, G-v is $\omega$-colourable
and $\alpha$-clique-coverable, where $\alpha$ (resp. $\omega$) is the size of a max stable set (resp. clique).
We then speculate whether separation routines for partitionable inequalities
could be practical for solving packing problem instances for dense $0,1$ matrices?

These papers provide a formal study of the border gateway protocol (BGP) which has become the defacto
standard for determining routes between different autonomous systems (i.e. organizations, or enterprises under
a common administrative control). Within an AS, protocols based on finding shortest paths are used for route
selection, and hence, like the Ford-Bellman algorithm, they are guaranteed to finally stabilize into
shortest path trees to each destination. The same is not true for BGP since the
nodes may order preferences on paths
arbitrarily. The SIGCOMM paper proposes a change to the protocol which provably eliminates one of the
reasons for instability observed in practice (due to MED attribute).
The solution was presented to the IETF.

Many coarse network designs are performed as follows. For each source-destination pair of nodes $s,t$ with
say $D$ traffic demand between them, reserve $D$ units of capacity on each link of a shortest $s-t$ path
in the network (topology). This reserved bandwidth is completely vulnerable, however, to any single link failure.
This paper generalizes the shortest path problem to natural
resilient path analogues. Several resilient (up to $k$ failures) versions are discussed including
the case where we must route traffic on a collection of disjoint paths. Here
a simple algorithm is described for the fractional version, and a $\frac{1}{14}$-approximation algorithm
is described for the integer version. It is also shown that it is NP-hard to obtain a polytime
$(\frac{1}{14}-\epsilon$)-approximation algorithm, for any $\epsilon >0$.
The longer version contains more discussion of alternative network resilience and restoration strategies.

It is shown how a couple of augmentation rules can be used to turn a multicommodity flow on a ring
(cycle graph) into a minimum cost such flow. Such combinatorial algorithms for exact minimum cost multicommodity
do not seem to exist, even in simple cases.

It is shown that finding the maximum number of a given set of $s}_{i},{t}_{i$ pairs that can
be connected by arc-disjoint paths in a directed graph cannot be approximated (in polytime) even within a factor
of $m}^{1/2-es\pi lon$ for any $\epsilon >0$. On the positive side, we describe a factor
$m}^{1/2$ approximation achievable by a greedy algorithm even in the presence of arc capacities
(a greedy such approximation was already known for unit capacities).

Originally motivated by routing in a passive optical ring network, we consider
the multicommodity flow problem in a node-capacitated ring. The cut condition
is not sufficient to characterize solvability of such instances. We show, however,
that it is sufficient to consider distance cut inequalities induced by $0,1,2$
node weights. We also see that a fractionally routable set of demands can
be integrally routed if we increase each node capacity by $1$.

Given a $0,1$ matrix $A$ with two $1\text{'}$ per row, when is it the case that the Chvatal closure
of the polytope $\{x:Ax\le 1,x\ge 0\}$ gives an integer polytope? This happens precisely when the rows
of $A$ determine a so-called t-perfect graph. No characterization of these graphs/matrices is known.
This paper characterizes those graphs for which every subgraph is t-perfect. This extends earlier
results on graphs with no $K}_{4$ minor. Schrijver has since shown
that the linear system for this class of graphs is also TDI (totaly dual integral).

These two papers (the first empirical, the latter theoretical) argue that the cost of wavelength converters
in a wavelength division multiplexed (WDM) network, is not warranted in static networks with large
fiber capacities (represented as many parallel edges). Also discussed, is the phenomenon that colouring
random instances of path intersection graphs is much easier in practice than colouring random instances
of graphs.

We describe a decomposition for cubic graphs that contain no minor isomorphic to the Petersen Graph
with one edge removed. This is used to show such graphs are 3-edge-colourable.

It is seen how a more general form of Lehman's theorem (only stated in Lehman's own paper on the topic, but whose
proof follows directly from the Seymour and Padberg presentations) can be translated to obtain
results for packing problems. In particular, this leads to a complete characterization of the stable
set polytope for graphs $G$, such that $G-N\left[v\right]$ is bipartite for each node $v$.

A graph is $4$-critical if it is not $3$-node colourable, but every proper subgraph is.
Toft conjectured (197?) that every such graph had a subgraph which is obtained from $K}_{4$ by subdividing
each edge an even number of times. This conjecture could be viewed as the natural analogue to
the fact that $G$ is bipartite only if it has no odd cycle. We prove the conjecture in the case
where such a graph has a node of degree $3$ (this was the first partial result).

Even, Itai and Shamir showed that in undirected graphs the following $4$-terminal edge-disjoint path (EDP) problem
is NP-hard: do there exist $k$ edge-disjoint paths,
$k\text{'}$ of which join terminals $s}_{1},{t}_{1$, and $k-k\text{'}$ of which join terminals $s}_{2},{t}_{2$?
A main consequence of this paper is that this problem is solvable for graphs on a fixed surface.

Schrijver gave a polytime method for determining the existence of disjoint paths between $k$ terminal pairs for graphs embedded on a fixed surface and for fixed $k$. Schrijver's approach is to consider each homotopic pattern that the possible collections of disjoint paths may form. For each pattern, he then applies shifting techniques to see whether there is a solution to the problem. The number of homotopies required ostensibly grows exponentially (thus the reason for a fixed $k$). We show that even for non-fixed $k$, one may restrict to a polynomially bounded (in the size of the supply and demand graphs) number of homotopic patterns as long as the number of terminals is fixed.

An algorithm is given to determine for a given planar graph and nodes s,t, the maximum number of s-t paths
such that there is no edge joining internal nodes on distinct paths in the collection. For graphs on a fixed
surface, and with $k$ fixed, an algorithm is described to determine whether there exists such a collection
of $k$ paths. The fixed assumption can be dropped by applying the results from "Preselecting..." above.

Martin Grotschel in the early 1980's posed the following as one of the top outstanding questions in
polyhedral combinatorics.
Find a complete description for the stable set polytope of a claw-free graph
(there is no stable set of size $3$ in $N\left(v\right)$ for each $v$).
As every line graph is claw-free, such a system would generalize Edmonds Mathching Polyhedron Theorem.
Despite attempts by many, such a result remains elusive. In this paper a description, and compact formulation,
is given for graphs where for each $v$ there is no stable set of size $3$ amongst the nodes
at distance $2$ from $v$ (called distance claw-free).
This problem was solved in 2005!
The solution
came about
from the work of Seymour-Chudnovsky and Eisenbrand-Oriolo-Stauffer-Ventura.
It turned out that distance claw-free graphs formed a critical subclass in the solution.

We show that if a graph has minimum degree at least 2, and it is not one of 7 exception graphs,
then there exists a subset of $S$ of at most $(2/5)n$ nodes such that each node of $V-S$ is adjacent
to some node of $S$.

We answer a question from
*Open problems in number theory* by Richard Guy.
How many bishops are needed on an n by n chessboard to make sure that each
square can be attacked by one of them?