For any outerplanar graph we show there is capacitated tree which approximates every cut within a constant factor. We use this to find a constant-factor approximation to maximum weight disjoint paths (without congestion) in such graphs.

Beyond Submodular Maximization via One-Sided Smoothness

SODA 2021, with Mehrdad Ghadir and Richard Santiago

This is the first half of a paper originally released in 2019 as Beyond Submodular Maximization

A Parameterized Family of Meta-Submodular Functions

with Mehrdad Ghadiri and Richard Santiago. June 2020.

This is the second half of a paper originally released in 2019 as Beyond Submodular Maximization
Policy makers focus on stable strategies as the ones adopted by rational players. If there are many stable solutions, however, an important secondary question is how to select amongst them. We study this question for the multicommodity flow coalition game, introduced by Papadimitriou to model incentives and cooperation between autonomous systems in the Internet. In short, the strategies of the game are flows in a capacitated network (the supply graph). The payoff to any node is the total flow which it terminates. Markakis and Saberi show that this game is balanced and hence has a non-empty core by Scarf's Theorem. In the transferable utility (TU) version this also leads to a polynomial-time algorithm to find core elements but for the application to autonomous systems, side payments are not natural. Finding core elements in NTU games, however, tends to be computationally much more difficult. Even for this multiflow game, the only previous result is due to Yamada and Karasawa who give a procedure to find a core element when the supply graph is a path. We extend their work by designing an algorithm, called Incorporate, which produces many different core elements. We use our algorithm to evaluate several specific instances by running Incorporate to generate multiple core vectors. We call these the empirical core of the game. We find that sampled core vectors are more consistent with respect to social welfare (SW) than for fairness (minimum payout). For SW they tend to do as well as the optimal linear program value. In contrast, there is a larger range across fairness in the empirical core; the fairness values tend to be worse than the optimal fairness LP value. We study this discrepancy in the setting of general graphs with single-sink demands. We give an algorithm which produces core vectors that simultaneously maximize SW and fairness. This leads to the following bicriteria result for general games.Given any core-producing algorithm and any $lambda in (0,1)$, one can produce an approximate core vector with fairness (resp. social welfare) at least the optimal LP values.

Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

with L. Séguin-Charbonneau. Mathematical Programming, May 2020. Earlier version in Foundations of Computer Science, FOCS 2011.

Garg Vazarani and Yannakakis showed that the integrality gap for (the natural LP relaxation of) maximum disjoint paths (MEDP) in planar graphs is Ω(n). Noting that their gap example (the grid) all but disappears if edge congestion 2 is allowed, Kleinberg and Tardos asked if MEDP in planar graphs behaves better when one admits constant congestion. A sequence of results ultimately showed that with constant (in fact 4) congestion, the integrality gap is O(1). Building on this result, we give a tight bound in terms of congestion. That is, if edge capacities in a planar graph are at least 2, then the integrality gap for MEDP is constant.

Multivariate Submodular Optimization

with Richard Santiago, ICML 2019.

When Do Gomory-Hu Subtrees Exist?

with Guyslain Naves, submitted Nov. 2019.

Gomory-Hu (GH) Trees are a classical sparsification technique for graph connectivity. It is one of the fundamental models in combinatorial optimization which also continually finds new applications, most recently in social network analysis. For any edge-capacitated undirected graph $G=(V,E)$ and any subset of {\em terminals} $Z \subseteq V$, a Gomory-Hu Tree is an edge-capacitated tree $T=(Z,E(T))$ such that for every $u,v \in Z$, the value of the minimum capacity $uv$ cut in $G$ is the same as in $T$. Moreover, the minimum cuts in $T$ directly identify (in a certain way) those in $G$. It is well-known that we may not always find a GH tree which is a subgraph of $G$. For instance, every GH tree for the vertices of $K_{3,3}$ is a $5$-star. We characterize those graph and terminal pairs $(G,Z)$ which always admit such a tree. We show that these are the graphs which have no \emph{terminal-$K_{2,3}$ minor}. That is, no $K_{2,3}$ minor whose vertices correspond to terminals in $Z$. We also show that the family of pairs $(G,Z)$ which forbid such $K_{2,3}$ ``$Z$-minors'' arises, roughly speaking, from so-called Okamura-Seymour instances. More precisely, they are subgraphs of {\em $Z$-webs}. A $Z$-web is built from planar graphs with one outside face which contains all the terminals and each inner face is a triangle which may contain an arbitrary graph. This characterization yields an additional consequence for multiflow problems. Fix a graph $G$ and a subset $Z \subseteq V(G)$ of terminals. Call $(G,Z)$ {\em cut-sufficient} if the cut condition is sufficient to characterize the existence of a multiflow for any demands between vertices in $Z$, and any edge capacities on $G$. Then $(G,Z)$ is cut-sufficient if and only if it is terminal-$K_{2,3}$ free.

Multi-agent Submodular Optimization

with Richard Santiago, APPROX 2018.

Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem

with A. Vetta, G.T. Wilfong, FOCS 2015.

We give a polylogarithmic approximation for capacitated confluent flows when the no-bottleneck assumption (NBA) holds. We show that a similar approximation holds when NBA is dropped if congestion 2 is allowed.
We show that the maximum single-sink unsplittable (or priority or confluent) flow problem is ``polynomial hard'' if the no-bottleneck assumption (NBA) is not satisfied. This holds even if all demands must lie in a range [1,1+ε] for some ε>0. This is quite sharp since if all demands are 1, this becomes a maximum flow problem. We then show that single-sink confluent flows are inapproximable to within a polylog factor even if the NBA holds.

Co-Location-Resistant Clouds

with Y. Azar, S. Kamara, I. Menache, M. Raykova, ACM Cloud Computing Security Workshop 2014.

A scheme is proposed to protect client virtual machines from being "attacked" by malicious VMs who try to co-locate on the same server.

Maximum Edge-Disjoint Paths in k-Sums of Graphs

with C. Chekuri, G. Naves, ICALP 2013.

The well-known grid example of Garg-Vazriani-Yannakakis shows that the integrality gap for the natural LP formulation of the undirected maximum edge-disjoint paths problem is $\Omega(\sqrt{n})$ even in planar graphs. Chekuri, Khanna and Shepherd established that a constant factor gap hols in planar graphs if edge-congestion $4$ is allowed. It is natural to ask for which classes of graphs does such a constant-factor constant-congestion hold. Its easy to deduce that for given constant bounds on the approximation and congestion, the class of ``nice'' graphs is minor-closed. Is the converse true? Does every minor-closed class exhibit such a constant factor/congestion bound relative to the LP formulation? One stumbling block for this problem is the fact that such bounds were not known for bounded treewidth graphs. In this paper we give a polytime algorithm which takes a fractional routing solution in a bounded treewidth graph and is able to integrally route (with congestion 1!) a constant fraction of the LP solution's value. This is the only such congestion 1 result known (apart from trees). The arguments also work for $k$-sums of graphs in some family, as long as the graph family has a constant factor/congestion bound. We use this to obtain such bounds hold for the class of $k$-sums of bounded genus graphs.

A Tight Lower Bound for Online Vector Bin Packing

with Y. Azar, I. Cohen, and S. Kamara, STOC 2013.

We resolve the longstanding gap on the competitive ratio for d-dimensional online vector bin packing (VBP). The best lower bound was 2 compared with the best upper bound of d+.7. When the bin sizes B are 1, we use a lower bound for online colouring (Halldorosson and Szegedy, 1992) and an idea of preparing'' for future adjacencies to easily get a d lower bound. This is boosted to d1-eps using an idea from (Dean-Goemans-Vondrak, 2005) in their work on approximability of stochastic packing integer programs. The lower bounds are more intricate in the cases when B2. We give almost matching upper bounds of O(Bd1/Blogn) in that case.

Shortest path versus Multi-hub Routing in Networks with Uncertain Demand

with A. Fréchette, M. Thottan, P. Winzer, To appear Transactions on Networking, Preliminary version in Infocom 2013.

We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on designing the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). This model may be too conservative if additional information on traffic patterns is available. Another extreme is the fixed demand model, where one designs the network to support peak point-to-point demands. We introduce a capped hose model to explore a broader range of traffic matrices which includes the above two as special cases. It is known that optimal designs for the hose model are always determined by single-hub routing, and for the fixed-demand model are based on shortest-path routing. We shed light on the wider space of capped hose matrices, in order to see which traffic models are more shortest path-like as opposed to hub-like. In order to address the space in between, we use hierarchical multi-hub routing templates, a generalization of hub and tree routing. In particular, we show that by adding peak capacities into the hose model, the single-hub tree-routing template is no longer cost-effective. This initiates the study of a class of robust network design ($\rnd$) problems restricted to these templates. Our empirical analysis is based on a heuristic for this new hierarchical $\rnd$ problem. We also propose that it is possible to define a routing indicator that accounts for the strengths of the marginals and peak demands and use this information to choose the appropriate routing template. We benchmark our approach against other well-known routing templates, using representative carrier networks and a variety of different capped hose traffic demands, parameterized by the relative importance of their marginals as opposed to their point-to-point peak demands. This study also reveals conditions under which multi-hub routing gives improvements over single-hub and shortest-path routings.

The VPN Conjecture is True

with Navin Goyal and Neil Olver. Journal of the ACM, Vol. 60-3, (2013). Preliminary version in Symposium on Theory of Computing STOC 2008.

We want to build a network that can transport any demand matrix (Dij) where jDijbi. The bi's are called marginals - they simply indicate that the total demand (traffic) involving node i is at most bi. 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 All-or-Nothing Multicommodity Flow Problem

with C. Chekuri, S. Khanna, Siam J. Computing, Vol. 42-4, (2013), pp 1467-1493. Preliminary version in Proceedings of STOC 2004.

The maximum edge-disjoint path problem (EDP) consist of a supply graph and some terminal pairs si,ti 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-ε (where m is the number arcs and any ε>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.

Flow-Cut Gaps for Integer and Fractional Multiflows

with C. Chekuri and C. Weibel. Journal of Combinatorial Theory, B., Vol. 103-2, (2013), pp 248-273. Prelimiary version in SODA 2010 .

We study a detailed model for virtual machine migration in tree (or near tree) topologies. Our algorithms lead to scalable heuristics with promising empirical results on a large topology.

Strategic network formation and local peering contracts

with E. Anshelevich, G. Wilfong. Games and Economic Behaviour, Vol. 73-1, (2011), pp 17-38. Preliminary version appeared in: Foundations of Computer Science, FOCS 2006.

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

Approximability of Robust Network Design

with N. Olver. To appear Mathematics of Operations Research. Preliminary version in: ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.

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).

Buy-at-Bulk Network Design with Protection

with Chandra Chekuri, Spyros Antonakapoulos, and Lisa Zhang. Mathematics of Operations Research. (2011). Preliminary version in: Foundations of Computer Science FOCS 2007.

Dynamic vs Oblivious Routing in Network Design

with Navin Goyal and Neil Olver, Algorithmica Volume 61, pp. 161--173, (2011). 17th Annual European Symposium on Algorithms (ESA 2009).

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Ω(log{n}) 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}.

Single Sink Multicommodity Flow with Side Constraints

Chapter in: Research Trends in Combinatorial Optimization. William Cook, Laszlo Lovasz, Jens Vygen (Editors); Springer, Berlin 2009.

In recent years, several new models for network flofws 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.

Edge-disjoint paths in planar graphs with constant congestion

with C. Chekuri, S. Khanna. SIAM J. Computing, Volume 39, Issue 1, pp. 281-301 (2009) (invited issue for STOC 2006.)

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 n if capacities are at most 1).

Approximate Integer Decompositions for Undirected Network Design Problems

with C. Chekuri, SIAM J. Discrete Math. Volume 23, Issue 1, pp. 163-177 (2008).

Degree-constrained network flows

with P. Donovan, A. Vetta, G. Wilfong. Symposium on the Theory of Computation, STOC 2007.

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(log(n)). 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 β-confluent flow problem for β[0,1]. Here we require that a β 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 β[12,1), there is a β-confluent flow of congestion at most (1+β1-β).

Island hopping and path colouring, with applications to WDM network design

with A. McGregor. Symposium on Discrete Algorithms, SODA 2007.

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).

A Note on Multiflows and Treewidth

with C. Chekuri and S. Khanna. Algorithmica, Volume 54, Issue3, Page 400, 2009.

Selective Randomized Load Balancing and Mesh Networks with Changing Demands

with P. Winzer. Journal of Optical Networking Vol. 5, Issue 5, pp. 320-339, 2006.

Robust Network Design and Selective Randomized Load Balancing

with P. Oswald, P. Winzer, M. Zirngibl. The 31st European Conference on Optical Communications (ECOC 2005) SECC, Glasgow, Scotland 25-29 September 2005.

Design Tools for Transparent Optical Networks

Chandra Chekuri, Paul Claisse, Rene Essiambre, Steven Fortune, Dan Kilper, Karun Nithi, Wonsuck Lee, Iraj Saniee, Bruce Shepherd, Gordon Wilfong, Chris White, Lisa Zhang. Bell Labs Technical Journal. Volume 11, Issue 2, 129-143, (2006)

An O(sqrt n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow

with C. Chekuri, S. Khanna, Theory of Computing 2/7, pp. 137-146 (2006).

Hardness of Robust Network Design

with C. Chekuri, G. Oriolo, M.G. Scutella, Networks, vol. 50, no. 1, (2007), 50-54. Preliminary version in: INOC 2005.

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 Dij. 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).

Edge-Disjoint Paths in Planar Graphs

with C. Chekuri, S. Khanna, FOCS 2004 .

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 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).

Content Distribution for Seamless Transmission

with E.G. Coffman, A. Constantinides, D. Rubenstein, D. Stavrou, Mathematical performance Modeling and Analysis, MAMA 2004 .

Lighting Fibers in a Dark Network

with Adrian Vetta, Journal on Selected Areas in Communication , Vol. 22, Number 9, 1583-1588, 2004.

The Demand Matching Problem

with A. Vetta Mathematics of Operations Research Vol. 32, No. 3, August 2007, pp. 563-578. Preliminary version in IPCO 2002.

We introduce the following problem. Given a graph G where each node v has a capacity b(v), and we are also given a set of edges F where each such fF also comes with an integer demand d(f) and weight w(f). 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(v). 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.

Directed Network Design Problems with Orientation Constraints

with S. Khanna, S. Naor, To appear: SIAM Journal for Discrete Mathematics, vol. 19 (1), 245-57, 2005. (Preliminary version in: SODA '99, San Francisco, January 1999, )

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.

Bipartite domination and Simultaneous Matroid Covers

with C.W. Ko, SIAM Journal for Discrete Mathematics, Vol. 16, No. 4, 517-523, 2003.

Visualizing, Finding and Packing Dijoins

with A. Vetta, Chapter in: Graph Theory and Combinatorial Optimization, GERAD 25th Anniversary Volumes, Springer 2005.

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.

Multicommodity Demand Flow in a Tree and Packing Integer Programs

with C. Chekuri, M. Mydlarz; ACM Transactions on Algorithms (TALG), 3(3), 2007. (Preliminary version in: ICALP 2003 )

We consider the multicommodity all-or-nothing flow problem in a tree. We are given a tree with integer edge capacities u(e) and a set F of demand edges f=uv, each with an integer d(f). A subset of demands is routable if no edge capacity is violated after each demand sends d(f) 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).

Cluster and Server Selection Using Passive Monitoring

with M. Andrews, A. Srinivasan, P. Winkler, F. Zane, Infocom 2002

A Fast and Scalable Approximation Algorithm for Computing Shared Recovery Flows Minimizing Long-Term Expected Cost

with L. Fleischer, A. Meyersen, I. Saniee, A. Srinivasan, CORC Report 2003-10

The Theta Body and Imperfection

Chapter in: Perfect Graphs: By Ramirez Alfonsion and Bruce Reed, Wiley and Sons Ltd., U.K. 2001

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 ω-colourable and α-clique-coverable, where α (resp. ω) 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?

Route Oscillations in I-BGP

with A. Basu, L. Ong, A. Rasala, G. Wilfong, SIGCOMM 2002; an article

The Stable Paths Problem and Interdomain Routing

with T.G. Griffin, G.T. Wilfong. IEEE/ACM Transactions on Networking, vol. 10 (2), 2002, 232-243. Policy Disputes in Path-Vector Protocols, (Earlier version) International Conference on Network Protocols, ICNP '99.

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.

Some strategies for reserving resilient capacity

with G. Brightwell, G. Oriolo. SIAM J. Discrete Math., , Vol. 14, No. 4, 524-539, 2001. A fuller, earlier version describes a number of alternative strategies for different types of restoration architectures.

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 114-approximation algorithm is described for the integer version. It is also shown that it is NP-hard to obtain a polytime (114-ε)-approximation algorithm, for any ε>0. The longer version contains more discussion of alternative network resilience and restoration strategies.

Reserving Resilient Capacity for a Single Commodity with Upper Bound Constraints

with G. Brightwell, G. Oriolo. Networks, vol 41. no.2 (2003), pp 87-96.

An Augmentation Algorithm for Mincost Multicommodity Flow on a Ring

with Lisa Zhang. Discrete Applied Mathematics 110, 2001, 301-315 (also Globecomm '99, High Speed Networks, Rio de Janeiro, Brazil,Dec. 99 ).

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.

Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems

with Venkat Guruswami, Sanjeev Khanna, Raj Rajaraman, Mihalis Yannakakis. Journal of Computer and System Sciences, Volume 67, Issue 3, Nov. 2003, Pages 473-652. (also in Proc. 31st Annual ACM Symposium on Theory of Computing (STOC) , pp. 19-28, 1999)

It is shown that finding the maximum number of a given set of si,ti pairs that can be connected by arc-disjoint paths in a directed graph cannot be approximated (in polytime) even within a factor of m1/2-esπlon for any ε>0. On the positive side, we describe a factor m1/2 approximation achievable by a greedy algorithm even in the presence of arc capacities (a greedy such approximation was already known for unit capacities).

Node-capacitated multicommodity routing for a ring

with V. Tandon, A. Frank, Z. Vegh. Math. of Operations Research , Vol. 27, No. 2, May 2002, 372-383.

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.

The graphs with all subgraphs t-perfect

with A.M.H. Gerards. Siam Journal of Discrete Mathematics, Vol. 11, No. 4, 1998, 524-545.

Given a 0,1 matrix A with two 1' per row, when is it the case that the Chvatal closure of the polytope {x:Ax1,x0} 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 K4 minor. Schrijver has since shown that the linear system for this class of graphs is also TDI (totaly dual integral).

Strong orientations without even directed circuits

with A.M.H. Gerards. Discrete Mathematics, vol. 188, 1998, 111-125.

Face extensions in planar cubic graphs

with K. Kilakos. Discrete Mathematics, vol. 181, 1998, 179-191.

The Gallai-Younger Conjecture holds for planar graphs

, with B.Reed. Combinatorica, vol. 16, 1996, 555-566.

Routing and configuration of static path optical transport networks

with E.Lowe, N. Walker. IEE Electronic Letters, vol. 32, 1996, 1913-1914.

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.

Excluding minors in cubic graphs

with K. Kilakos. Combinatorics, Computing and Probability, vol. 3, 1996, 57-58.

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.

Applying Lehman's theorem to packing problems

Mathematical Programming, vol. 71, 1995, 353-366.

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[v] is bipartite for each node v.

Subdivisions and the chromatic index of r-graphs

with K.Kilakos. Journal of Graph Theory, vol 22, 1996, 203-211

Right angle free subsets in the plane

with A. Gamble, W. Pulleyblank, B. Reed. Graphs and Combinatorics, vol. 11, 1995, 121-129.

A note on a conjecture of Toft

with T.R. Jensen. Combinatorica, vol. 15, 1995, 373-377.

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 K4 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).

A note on clutter partitions

Operations Research Letters, vol. 15, 1994, 127-131.

Near-perfect matrices

Mathematical Programming, vol. 64, 1994, 295-323.

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' of which join terminals s1,t1, and k-k' of which join terminals s2,t2? 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.

Induced circuits in planar graphs

with C. McDiarmid, B. Reed, A. Schrijver. Journal of Combinatorial Theory (B), vol. 60, 1994, 169-176.

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.

Formulations for the stable set polytope

with W. Pulleyblank. Proceedings of Integer Programming and Combinatorial Optimization '93, Erice, Italy 1993).

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(v) 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.

On splitable sets

with W. Pulleyblank, B. Reed. Graph Theory Notes of New York XXIII, Eds. J.W. Kennedy, Louis V. Quintas, New York Academy of Sciences 1992, 11-20.

Non-interfering network flows

with C.McDiarmid, B. Reed, A.Schrijver. Scandinavian Workshop on Algorithm Theory (SWAT 92), Helsinki, July 8-10, 1992.

Hamiltonicity in claw-free graphs

Journal of Combinatorial Theory (B) vol. 53, 1991, 173-194.

Domination in graphs with minimum degree two

with W. McCuaig. Journal of Graph Theory, vol. 13, 1989, 749-762.

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.

Domination parameters for the bishops graph

with E.J. Cockayne and A.B. Gamble. Discrete Mathematics vol. 58, 1986, 221-227.

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?

An upper bound for the k-domination number of a graph

with E.J. Cockayne and A.B. Gamble. Journal of Graph Theory vol. 9, 1985, 533-534.

Domination of chessboards by queens on a column

with E.J. Cockayne and A.B. Gamble. Ars Combinatoria vol. 19, 1985, 105-118.