Schedule of the Connectivity Workshop

Monday, September 7

10:30 - 11:00 Registration & Welcome coffee
11:00 - 11:30 Wolfgang Mader: Critical vertices in k-connected digraphs
11:30 - 12:00 Victor Chepoi: Simple connectivity, local-to-global, and matroids
12:00 - 14:00 Lunch break
14:00 - 16:00 Discussion session
16:00 - 16:30 Tea and cake
16:30 - 17:00 Ahmad Abdi: Packing odd T-joins with at most two terminals
17:00 - 17:30 Tamás Király: Blocking optimal k-arborescences

Thursday, September 10

9:45 - 10:30 Rico Zenklusen: An O(1)-approximation for minimum spanning tree interdiction
10:30 - 11:00 Coffee break
11:00 - 11:30 András Sebő: Travelling salesmen on bounded degree trails
11:30 - 12:00 Jens Vygen: Reassembling trees for the traveling salesman
12:00 - 14:00 Lunch break
14:00 - 16:00 Discussion session
16:00 - 16:30 Tea and cake
16:30 - 17:00 Ken-ichi Kawarabayashi: Deterministic edge connectivity in near-linear time
17:00 - 17:30 Jørgen Bang-Jensen: Antistrong digraphs

Friday, September 11

9:45 - 10:30 Zoltán Szigeti: On (2k,k)-connected graphs
10:30 - 11:00 Coffee break
11:00 - 11:30 Andreas Emil Feldmann: A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs
11:30 - 12:00 Kanstantsin Pashkovich: A strongly polynomial (2+ε)-approximation algorithm for network design problems defined by proper functions
12:00 - 14:00 Lunch break
14:00 - 16:00 Discussion session
16:00 - 16:30 Tea and cake / end of workshop

Abstracts

(Underlined titles can be clicked for the video recording)

Let T be an even vertex subset, of size at most two, and let S be an edge subset of a graph. An edge subset is odd if it contains an odd number of edges of S. We are interested in packing edge-disjoint odd T-joins. The maximum size of such a packing is at most the size of a minimum cover. Guenin and I have shown that equality holds when a certain parity condition is satisfied and two minors are excluded.

Our result implies Guenin's characterization of weakly bipartite graphs, and has applications to packing two-commodity paths and T-joins with at most 4 terminals, as well as covering edges using cuts. In this talk, I will briefly talk about these applications but the focus will be to provide an overview of the proof, which uses the vertex version of Menger's theorem, the 2-linkage theorem by Seymour and Thomassen, as well as "disentangling" techniques used previously by Geelen, Guenin and Schrijver.

Top

Hyung-Chan An: Dynamic facility location via exponential clocks

The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the "stability" of the solution: there is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches.

We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on the clients and facilities, and connect every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP-roundings for facility location problems. In particular, we use no clustering and we allow clients to connect through paths of arbitrary lengths. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem.

Joint work with Ashkan Norouzi-Fard and Ola Svensson.

Top

An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that one can decide in linear time whether they are connected by an antidirected trail. A digraph D is antistrong if it contains an antidirected (x,y)-trail starting and ending with a forward arc for every choice of x,y ∈ V(D). We show that antistrong connectivity can be decided in linear time. We discuss relations between antistrong connectivity and other properties of a digraph and show that the arc-minimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arc-set. We show that one can determine in polynomial time the minimum number of new arcs whose addition to D makes the resulting digraph the arc-disjoint union of k antistrong digraphs. In particular, we determine the minimum number of new arcs which need to be added to a digraph to make it antistrong. We use results from matroid theory to characterize graphs which have an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. This immediately gives analogous results for graphs which have a connected bipartite 2-detachment.

Top

We study the existence of a polynomial-time algorithm for computing a mixed Nash equilibrium of the following two player zero sum game. A network is given, together with k source-destination pairs si-ti. The first player, called the designer, must choose one si-ti path for every i, and the second player, called the attacker, must choose c edges (c is also given). The attacker's payoff is the number of intercepted paths (and intercepting a path more than once does not help him).

We present special cases of this problem that have been solved. Precisely, the case k=1 reduces to Max-Flow, and in undirected graphs, Hu's two commodity flows can be used to solve the case k=2. The case c=1 has concurrent flows/Sparsest Cut linear programs and again polynomial-time algorithms exists. The general case is open.

Top

The notion of element-connectivity has found several important applications in network design and routing problems. We focus on a reduction step that preserves the element-connectivity due to Hind and Oellerman which when applied repeatedly allows one to reduce the original graph to a simpler one while preserving the element connectivity. This pre-processing step is a crucial ingredient in several applications. We revisit this reduction step and provide a new proof via the use of setpairs. Our main contribution is algorithmic results for several basic problems on element-connectivity including the problem of achieving the aforementioned graph simplification. We utilize the underlying submodularity properties of element-connectivity to derive faster algorithms. The main goal of the talk is to popularize the several open problems on this topic.

Joint work with Thapanapong Rukkanchanunt and Chao Xu.

Top

A basis graph of a matroid M is the graph G(M) having the bases of M as the vertex-set and the pairs of bases differing by an elementary exchange as edges. Basis graphs of matroids have been characterized by S.B. Maurer, J. Combin. Th. Ser. B 14 (1973) using two local conditions and global metric condition (called the "positioning condition''). Maurer conjectured that the positioning condition can be replaced by simple connectivity of the triangle-square complex of G(M). We will confirm this conjecture and establish the following local-to-global characterization of basis graphs:

Theorem: A finite graph G is the bais graph of a matroid if and only if the triangle-square complex X(G) of G is simply connected and every ball of radius 3 of G are isomorphic to a ball of radius 3 in a basis graph of a matroid.

The talk is based on the paper J. Chalopin, V. Chepoi, D. Osajda, On two conjectures of Maurer concerning basis graphs of matroids, J. Comb. Theory, Ser. B 114 (2015), 1–32.

Top

Graphs with bounded highway dimension were introduced in [Abraham et al., SODA 2010] as a model of transportation networks. We show that any such graph can be embedded into a distribution over bounded treewidth graphs with arbitrarily small distortion. More concretely, if the highway dimension of G is constant we show how to randomly compute a subgraph of the shortest path metric of the input graph G with the following two properties: it distorts the distances of G by a factor of 1+ε in expectation and has a treewidth that is polylogarithmic in the aspect ratio of G. In particular, this result implies quasi-polynomial time approximation schemes for a number of optimization problems that naturally arise in transportation networks, including Travelling Salesman, Steiner Tree, and Facility Location.

To construct our embedding for low highway dimension graphs we extend Talwar’s [STOC 2004] embedding of low doubling dimension metrics into bounded treewidth graphs, which generalizes known results for Euclidean metrics. We add several non-trivial ingredients to Talwar’s techniques, and in particular thoroughly analyze the structure of low highway dimension graphs. Thus we demonstrate that the geometric toolkit used for Euclidean metrics extends beyond the class of low doubling metrics.

Top

We address the following two multiflow problems:

(i) The minimum cost node-demand multiflow problem.

(ii) The maximum node-capacitated free multiflow problem.

For (i), we develop an O(n log(n AC) MF(kn, km)) time algorithm for a network of n nodes, m edges, k terminals, the maximum A of edge-cost, and the sum C of edge-capacity, where MF(n',m') is the time complexity of solving the maximum flow problem for a network of n' nodes and m' edges.

For (ii), we develop an O((m log k) MSF(n,m,1)) time algorithm for a network of n nodes, m edges, and k terminals, where MSF(n,m,h) is the time complexity of solving the maximum submodular flow problem on a network of n nodes, m edges, and time complexity h of computing the exchange capacity of the defining submodular function. By Fujishge-Zhang algorithm for submodular flow, we obtain an O(m n3 log k) time algorithm for (ii).

Our algorithms are designed on the basis of a developing theory of discrete convex functions on certain graph structures, and bring "ellipsoid-free" combinatorial implementations to approximation algorithms of related network design problems.

Top

We present a deterministic algorithm that computes the edge-connectivity of a graph in near-linear time. This is for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. Our algorithm is easily extended to find a concrete minimum edge-cut. In fact, we can construct the classic cactus representation of all minimum cuts in near-linear time.

The previous fastest deterministic algorithm by Gabow from STOC'91 took Õ(m+λ2n), where λ is the edge connectivity, but λ can be as big as n-1.

At STOC'96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm and compare sizes.

Our main technical contribution is a near-linear time algorithm that contracts vertex sets of a simple input graph G with minimum degree δ, producing a multigraph Ḡ with Õ(m/δ) edges which preserves all minimum cuts of G with at least two vertices on each side.

In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.

Joint work with Mikkel Thorup.

Top

Given a digraph D=(V,A) and a positive integer k, an arc set F ⊆ A is called a k-arborescence if it is the disjoint union of k spanning arborescences. The problem of finding a minimum cost k-arborescence is known to be polynomial-time solvable using matroid intersection. In this talk we study the following problem: find a minimum cardinality subset of arcs that contains at least one arc from every minimum cost k-arborescence. For k=1, the problem was solved in [A. Bernáth, G. Pap, Blocking optimal arborescences, IPCO 2013]. We give an algorithm for general k that has polynomial running time if k is fixed. Joint work with Attila Bernáth.

Top

In the multiway cut problem, input is an edge/node weighted graph and a set of k terminals; the goal is to remove min-weight subset of edges/nodes such that there is no path between any two terminals. Directed multiway cut (Dir-MC) admits 2-approximation and node-weighted multiway cut (Node-MC) admits 2(1-1/k) approximation. Previous rounding algorithms for these problems are based on careful rounding of an "optimum" solution to an LP relaxation. We describe extremely simple and near linear-time rounding algorithms with same approximation ratio via a natural distance based LP relaxation. Additionally, we also prove that the integrality gap of the LP relaxation for Dir-MC is 2 even in directed planar graphs with two terminals (k=2).

Joint work with Chandra Chekuri.

Top

It is proved that every non-complete, finite digraph of connectivity number k has a fragment F containing at most k critical vertices. The following result is a direct consequence: every k-connected, finite digraph D of minimum out- and indegree at least 2k + m - 1 for positive integers k, m has a subdigraph H of minimum outdegree or minimum indegree at least m - 1 such that D - x is k-connected for all vertices x of H. For m = 1, this implies immediately the existence of a vertex of indegree or outdegree less than 2k in a k-critical, finite digraph.

Top

In the tree augmentation problem (TAP) we are given a tree T (a laminar family) on node set V and an edge set E on V. The goal is to augment T by a min-size edge-set F ⊆ E such that T+F is 2-edge-connected. In the weighted version of the problem (weighted TAP), F should be of minimum weight. Weighted TAP is currently a "threshold" problem in connectivity network design. It is the simplest problem for which ratio better than 2 is not known, but is suspected to exist – since TAP admits ratio 1.5. In this talk I will describe a relatively simple LP-relaxation for the problem, and a dual-fitting 1.75-approximation algorithm for (unweighted) TAP that is based on this LP-relaxation.

Top

For finding a minimum cost edge set having at least a required number of edges in each cut, Jain gave a 2-approximation algorithm, whenever the requirements are defined by a proper function. The algorithm of Jain is based on linear programming. Williamson et.al. provided a combinatorial algorithm with guarantee 2H(k), where H(.) is the harmonic number and k is the maximum value of the proper function.

We give a strongly polynomial (2+ε)-approximation algorithm; for this problem. Our algorithm is based on the ideas of Jain and multiplicative weight method of Garg, Koenemann.

Joint work with Andreas Feldman, Laura Sanita, Jochen Koenemann.

TopTop

Homomorphisms of connected graphs, possibly under constraints, onto a graph G, reflect connectivity properties of G. For instance, a graph is the homomorphic image of a tree with all degrees at most k=2 (a path), if and only if it is connected and has at most two vertices of odd degree. We call a homomorphism of a tree with all degrees at most k onto the vertex set of G, a k-trail. (This may be interpreted as a problem of groups of salesmen allowed to split into at most k-1 groups in each vertex.) This notion has been defined under the name of "bounded degree spanning hierarchies" and first approximation algorithms have been worked out by Molnár, Durand and Merabet.

We raise the problem of deciding whether a graph itself is a k-trail. The above given obvious answer for k=2 implies that the minimum weight of a 2-trail in an edge-weighted graph is equivalent to finding a TSP path of minimum length in the metric closure. Christofides' idea provides a 3/2-approximation algorithm for this problem.

For k=3, surprisingly, any 2-edge-connected graph is a 3-trail, moreover with all even degree vertices being the images of degree 2 vertices only. This is an easy consequence of splitting off in 2-edge-connected graphs, a simple special case for k=2 of Lovász's and Mader's lemmas. For general k the problem remains open. We prove previous and new approximation results using these connections.

Joint work with Miklós Molnár and Alantha Newman.

Top

We investigate two problems addressing combined connectivity augmentation and orientations settings. We give a polynomial time 6-approximation algorithm for finding a minimum cost subgraph of an undirected graph G that admits an orientation covering a nonnegative crossing G-supermodular demand function. An important example is (k,l)-edge-connectivity. Our algorithm is based on a non-standard application of the iterative rounding method, requiring a new type of uncrossing on partitions and co-partitions. We also consider the problem setting when the cost of an edge can be different for the two possible orientations. We disprove an earlier conjecture by Khanna, Naor and Shepherd, showing a large integrality gap already in simple settings.

Joint work with Laci Vegh.

Top

A graph G is called (2k,k)-connected if G is 2k-edge-connected and G-v is k-edge-connected for every vertex v. The study of (4,2)-connected graphs is motivated by a theorem of Thomassen which states that a graph has a 2-vertex-connected orientation if and only if it is (4,2)-connected.

In this talk, we provide a construction of the family of (2k,k)-connected graphs for k even which generalizes the construction given by Jordán for (4,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph G and an integer k>1, what is the minimum number of edges to be added to make G (2k,k)-connected. Both these results are based on a new splitting-off theorem for (2k,k)-connected graphs.

Joint work with Olivier Durand de Gevigney.

Top

Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex combination of spanning trees. The main argument then is that randomly sampling a tree from such a distribution and then completing the tree to a tour at minimum cost yields a better approximation guarantee than simply taking a minimum cost spanning tree (as in Christofides' algorithm). We argue that an additional step can help: reassembling the spanning trees before sampling. Exchanging two edges in a pair of spanning trees can improve their properties under certain conditions. We demonstrate the usefulness for the metric s-t-path TSP by devising a deterministic polynomial-time algorithm that improves on Sebős previously best approximation ratio of 8/5.

Top

Given n points (xi,yi) ∈ ℝ2 with weights wi of arbitrary sign, the problem is to find a convex set C ⊂ ℝ2 that maximizes ∑(xi,yi)∈C wi. Known results include an O(n3) algorithm for the problem based on an earlier O(kn3) algorithm to find an optimal convex k-gon. Both the above algorithms and our approach work on describing the boundary of C. We provide a polyhedral (network flow) description of the problem of finding a longest directed cycle subject to constraints linking adjacent arcs, that includes the maximum convex subset problem as a special case.

This is joint work with Maurice Queyranne.

Top

Network interdiction studies the maximum impact that a removal of a limited number of edges or vertices can have on a graph optimization problem. Most interdiction problems are NP-hard, and only little is known about their approximability. One of the oldest and most-studied interdiction problems is minimum spanning tree (MST) interdiction. Here, an MST problem on a multigraph is given together with positive edge costs and a budget B. The goal is to remove edges of total cost at most B such that MSTs in the resulting graph are as heavy as possible. As we will highlight in the talk, MST interdiction is closely related to some classical graph disconnection problems, like the k-cut problem. So far, the best approximation was a nearly two-decades-old O(log(m))-approximation by Frederickson and Solis-Oba (SODA 1996), where m is the number of edges. In this talk we show that MST interdiction admits an O(1)-approximation.

Top

We show improved approximation guarantees for the traveling salesman problem on cubic graphs, and cubic bipartite graphs. For cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravi (2014) by giving a simple "local improvement'' algorithm that finds a tour of length at most 5/4n-2. For 2-connected cubic graphs, we show that the techniques of  Moemke and Svensson (2011) can be combined with the techniques of Correa, Larre and Soto (2012), to obtain a tour of length at most (4/3-1/8754)n.

Top