Search

We provide approximation algorithms for several variants of the Firefighter problem on general graphs. The Firefighter problem models the case where a diffusive process such as an infection (or an idea, a computer virus, a fire) is spreading through a network, and our goal is to contain this infection by using targeted vaccinations. Specifically, we are allowed to vaccinate at most a fixed number (called the budget) of nodes per time step, with the goal of minimizing the effect of the infection. The difficulty of this problem comes from its temporal component, since we must choose nodes to vaccinate at every time step while the infection is spreading through the network, leading to notions of “cuts over time”. We consider two versions of the Firefighter problem: a “non-spreading” model, where vaccinating a node means only that this node cannot be infected; and a “spreading” model where the vaccination itself is an infectious process, such as in the case where the infection is a harmful idea, and the vaccine to it is another infectious beneficial idea. We look at two measures: the MaxSave measure in which we want to maximize the number of nodes which are not infected given a fixed budget, and the MinBudget measure, in which we are given a set of nodes which we have to save and the goal is to minimize the budget. We study the approximability of these problems in both models.

We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an $O(2^{6.903\sqrt{n}})$ time algorithm solving weighted Hamiltonian Cycle on an n-vertex planar graph. Similar technique solves Planar Graph Travelling Salesman Problem with n cities in time $O(2^{9.8594\sqrt{n}})$ . Our approach can be used to design parameterized algorithms as well. For example, we give an algorithm that for a given k decides if a planar graph on n vertices has a cycle of length at least k in time $O(2^{13.6\sqrt{k}}n+n^{3})$ .

In this paper, we study the problems of enumerating cuts of a graph by non-decreasing weights. There are four problems, depending on whether the graph is directed or undirected, and on whether we consider all cuts of the graph or only s-t cuts for a given pair of vertices s,t. Efficient algorithms for these problems with $\tilde{O}(n^{2}m)$ delay between two successive outputs have been known since 1992, due to Vazirani and Yannakakis. In this paper, improved algorithms are presented. The delays of the presented algorithms are O(nmlogź(n2/m)). Vazirani and Yannakakis's algorithms have been used as basic subroutines in the solutions of many problems. Therefore, our improvement immediately reduces the running time of these solutions. For example, for the minimum k-cut problem, the upper bound is immediately reduced by a factor of $\tilde{O}(n)$ for k=3,4,5,6.

It is known that, given an edge-weighted graph, a maximum adjacency ordering (MA ordering) of vertices can find a special pair of vertices, called a pendent pair, and that a minimum cut in a graph can be found by repeatedly contracting a pendent pair, yielding one of the fastest and simplest minimum cut algorithms. In this paper, we provide another ordering of vertices, called a minimum degree ordering (MD ordering) as a new fundamental tool to analyze the structure of graphs. We prove that an MD ordering finds a different type of special pair of vertices, called a flat pair, which actually can be obtained as the last two vertices after repeatedly removing a vertex with the minimum degree. By contracting flat pairs, we can find not only a minimum cut but also all extreme subsets of a given graph. These results can be extended to the problem of finding extreme subsets in symmetric submodular set functions.

We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(δ(Π))−λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V|2) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs.

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X 1,…,X g ⊆V, with each group X i having a requirement r i between 0 and |X i |. The goal is to find a minimum cost set of edges whose removal separates each group X i into at least r i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4k n 3) time algorithm for this problem, significantly improving the previous algorithm of time $O(4^{k^{3}}n^{5})$for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n).

Let G=(V,E) be an undirected graph, and let B⊆V×V be a collection of vertex pairs. We give an incremental polynomial time algorithm to generate all minimal edge sets X⊆E such that every pair (s,t)∈B of vertices is disconnected in (V,E ∖ X), generalizing well-known efficient algorithms for generating all minimal s-t cuts, for a given pair s,t of vertices. We also present an incremental polynomial time algorithm for generating all minimal subsets X⊆E such that no (s,t)∈B is a bridge in (V,X∪B). Both above problems are special cases of a more general problem that we call generating cut conjunctions for matroids: given a matroid M on ground set S=E∪B, generate all minimal subsets X⊆E such that no element b∈B is spanned by E ∖ X. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V,E∪B), the more general problem of generating cut conjunctions for vectorial matroids turns out to be NP-hard.

We consider two multicriteria versions of the global minimum cut problem in undirected graphs. In the k-criteria setting, each edge of the input graph has k non-negative costs associated with it. These costs are measured in separate, non-interchangeable, units. In the AND-version of the problem, purchasing an edge requires the payment of _emphiall_/emph the k costs associated with it. In the OR-version, an edge can be purchased by paying erbany oneerb of the k costs associated with it. Given k bounds b1,b2,. . . ,bk, the basic multicriteria decision problem is whether there exists a cut C of the graph that can be purchased using a budget of bi units of the ith criterion, for 1 ≤ i ≤ k. We show that the AND-version of the multicriteria global minimum cut problem is polynomial for any fixed number k of criteria. The OR-version of the problem, on the other hand, is NP-hard even for k = 2, but can be solved in pseudo-polynomial time for any fixed number k of criteria. It also admits an FPTAS. Further extensions, some applications, and multicriteria versions of two other optimization problems are also discussed.

The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a min{O(n 2 log n logm), O(m 2 n 1.5 log2 n + k n)} time algorithm with a (2–2/k)-approximation ratio (clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(n k3 + (n log n)k 2) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation algorithm of Dahlhaus et al. (for general graphs) takes O(k n 2 log n) time when applied to planar graphs. Our approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm) factor (m \le k).

This paper presents algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of an undirected weighted graph G . Let G=(V, E) be an undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k -way cut problem with fixed k , that requires O(n 4 ) and O(n 6 ) maximum flow computations, respectively, to compute a minimum 3 -way cut and a minimum 4 -way cut of G . In this paper we first show some properties on minimum 3 -way cuts and minimum 4 -way cuts, which indicate a recursive structure of the minimum k -way cut problem when k = 3 and 4 . Then, based on those properties, we give divide-and-conquer algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of G , which require O(n 3 ) and O(n 4 ) maximum flow computations, respectively.

Let G=(V,E) be a complete undirected graph, with node set V={v 1 , . . ., v n } and edge set E . The edges (v i ,v j ) ∈ E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = { k i } i=1 p $(\sum_{i=1}^p k_i \leq |V|$) , the minimum K-cut problem is to compute disjoint subsets with sizes { k i } i=1 p , minimizing the total weight of edges whose two ends are in different subsets. We demonstrate that for any fixed p it is possible to obtain in polynomial time an approximation of at most three times the optimal value. We also prove bounds on the ratio between the weights of maximum and minimum cuts.