Let c denote a non-negative constant. Suppose that we are given an edge-weighted bipartite graph G=(V,E) with its 2-layered drawing and a family X of intersecting edge pairs. We consider the problem of finding a maximum weighted matching M* such that each edge in M* intersects with at most c other edges in M*, and that all edge crossings in M* are contained in X. In the present paper, we propose polynomial-time algorithms for the problem for c=1 and 2. The time complexities of the algorithms are O((k+m)log n) for c=1 and O(m^4log n+k^3+n(k^2+log n)) for c=2, respectively, where n=|V|, m=|E| and k=|X|.
The conflict pair constraint (or negative disjunctive constraint ) is a generalization of the non-crossing constraint. Represented by a conflict graph @math , this constraint prohibits a solution from including two edges @math such that @math . The minimum cost perfect matching problem with conflict pair constraints is strong NP-hard for a general graph @math even if the conflict graph @math is a collection of single edges @cite_6 and is NP-hard even for @math that consists of 4-cycles @cite_24 ; it turns out that the problem is NP-hard for a bipartite graph. For this type of constraint, there are also studies on the transportation problem @cite_14 @cite_8 , the minimum spanning tree problem @cite_20 @cite_11 @cite_13 , and the max-flow problem @cite_19 .
@cite_14 @cite_8 @cite_6 @cite_24 @cite_19 @cite_13 @cite_20 @cite_11
2050524721 179052057 2046709864 1982713256 1977673015 2121815516 2898777864 2132936659 2173641041 2004779317 2247768113 2161190897 1867111234 2032349632 2033554386 2493870798 2229536649 2055636480 2787728049 1965734368
We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at least one arc has to carry flow in a feasible solution. It is convenient to represent the negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the arcs of the underlying graph, and whose edges encode the constraints. Analogously we represent the positive disjunctive constraints by a so-called forcing graph. For conflict graphs we prove that the maximum flow problem is strongly @math -hard, even if the conflict graph consists only of unconnected edges. This result still holds if the network consists only of disjoint paths of length three. For forcing graphs we also provide a sharp line between polynomially solvable and strongly @math -hard instances for the case where the flow values are required to be integral. Moreover, our hardness results imply that no polynomial time approximation algorithm can exist for both problems. In contrast to this we show that the maximum flow problem with a forcing graph can be solved efficiently if fractional flow values are allowed. For the classical minimum spanning tree problem we introduce disjunctive constraints for pairs of edges which can not be both included in the spanning tree at the same time. These constraints are represented by a conflict graph whose vertices correspond to the edges of the original graph. Edges in the conflict graph connect conflicting edges of the original graph. It is shown that the problem becomes strongly @math -hard even if the connected components of the conflict graph consist only of paths of length two. On the other hand, for conflict graphs consisting of disjoint edges (i.e. paths of length one) the problem remains polynomially solvable. We study approaches for the exact solution of the NP-hard minimum spanning tree problem under conflict constraints. Given a graph (G(V,E) ) and a set (C E E ) of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the edges from each pair in (C ). The problem was introduced recently in the literature, with several results on its complexity and approximability. Some formulations and both exact and heuristic algorithms were also discussed, but computational results indicate considerably large duality gaps and a lack of optimality certificates for benchmark instances. In this paper, we build on the representation of conflict constraints using an auxiliary conflict graph ( G (E,C) ), where stable sets correspond to conflict-free subsets of (E ). We introduce a general preprocessing method and a branch and cut algorithm using an IP formulation with exponentially sized classes of valid inequalities for both the spanning tree and the stable set polytopes. Encouraging computational results indicate that the dual bounds of our approach are significantly stronger than those previously available, already in the initial LP relaxation, and we are able to provide new feasibility and optimality certificates. We consider the minimum spanning tree problem with conflict constraints (MSTC). The problem is known to be strongly NP-hard and computing even a feasible solution is NP-hard. When the underlying graph is a cactus, we show that the feasibility problem is polynomially bounded whereas the optimization version is still NP-hard. When the conflict graph is a collection of disjoint cliques, (equivalently, when the conflict relation is transitive) we observe that MSTC can be solved in polynomial time. We also identify other special cases of MSTC that can be solved in polynomial time. Exploiting these polynomially solvable special cases we derive strong lower bounds. Also, various heuristic algorithms and feasibility tests are discussed along with preliminary experimental results. As a byproduct of this investigation, we show that if an @e-optimal solution to the maximum clique problem can be obtained in polynomial time, then a ([email protected])-optimal solution to the maximum edge clique partitioning (Max-ECP) problem can be obtained in polynomial time. As a consequence, we have a polynomial time approximation algorithm for the Max-ECP with performance ratio O(n(loglogn)^2log^3n), improving the best previously known bound of O(n). In this paper we address the minimum cost perfect matching problem with conflict pair constraints (MCPMPC). Given an undirected graph G with a cost associated with each edge and a conflict set of pairs of edges, the MCPMPC is to find a perfect matching with the lowest total cost such that no more than one edge is selected from each pair in the conflict set. MCPMPC is known to be strongly NP-hard. We present additional complexity results and identify new polynomially solvable cases for the general MCPMPC. Several heuristic algorithms and lower bounding schemes are presented. The proposed algorithms are tested on randomly generated instances. Encouraging experimental results are also reported. Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ+ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v∈V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra’s algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s–t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor @math the minimum number of arcs which has to be removed to guarantee d(s,t)≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and or node elimination. Abstract In this work we focus on an extension of the minimum cost flow problem in layered networks. Feasible arc flows must satisfy a specific compatibility restriction in addition to flow balance and capacity restrictions. Namely, at most one of the crossing arcs is allowed to have positive flow on it. This variant of the minimum cost flow problem, which we call the minimum cost noncrossing flow problem, can frequently be encountered in real life. The determination of optimal temporal quay crane allocations to berthed vessels in container terminals, and optimal train schedules through the stations on the same railroad line are two examples. We first analyze the complexity of the problem and show that the noncrossing flow problem is in fact N P -complete in a layered network. Then, we introduce mixed-integer linear programming formulations and discuss a polynomially solvable special case. Next we show a sufficient condition for the existence of a crossing in an optimal solution, which can be used for preprocessing the arcs in order to reduce the problem size. Our computational experiments on a large test set show that our preprocessing algorithm can significantly reduce the number of arcs. We consider a network creation game in which, each player (vertex) has a limited budget to establish links to other players. In our model, each link has a unit cost and each agent tries to minimize its cost which is its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two variants of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between that vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between that vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. Next, we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. For infinite numbers of n, we construct an equilibrium tree with diameter Θ(n) in the MAX version. Also, we prove that the diameter of any equilibrium tree is O(log n) in the SUM version and this bound is tight. When all vertices have unit budgets (i.e. can establish link to just one vertex), the diameter in both versions is O(1). We give an example of equilibrium graph in MAX version, such that all vertices have positive budgets and yet the diameter is as large as Ω(√log n). This interesting result shows that the diameter does not decrease necessarily and may increase as the budgets are increased. For the SUM version, we prove that every equilibrium graph has diameter 2O(√log n) when all vertices have positive budgets. Moreover, if the budget of every players is at least k, then every equilibrium graph with diameter more than 3 is k-connected. An instance of the k-Steiner forest problem consists of an undirected graph G = (V,E), the edges of which are associated with non-negative costs, and a collection D = (si,ti): 1 ≤ i ≤ d of distinct pairs of vertices, interchangeably referred to as demands. We say that a forest F ⊆ G connects a demand (si, ti) when it contains an si-ti path. Given a requirement parameter K ≤ |D|, the goal is to find a minimum cost forest that connects at least k demands in D. This problem has recently been studied by Hajiaghayi and Jain [SODA'06], whose main contribution in this context was to relate the inapproximability of k-Steiner forest to that of the dense k-subgraph problem. However, Hajiaghayi and Jain did not provide any algorithmic result for the respective settings, and posed this objective as an important direction for future research. In this paper, we present the first non-trivial approximation algorithm for the k-Steiner forest problem, which is based on a novel extension of the Lagrangian relaxation technique. Specifically, our algorithm constructs a feasible forest whose cost is within a factor of O(min n2 3, √d ċ log d) of optimal, where n is the number of vertices in the input graph and d is the number of demands. For a graph G and a collection of vertex pairs (s"1,t"1),...,(s"k,t"k) , the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P"i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3. Min-Sum: We extend recent results by Colin de Verdiere and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time. Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3. Constrained path problems have to do with finding paths in graphs subject to constraints. We present a constraint programming approach for solving the Ordered disjoint-paths problem (ODP), i.e., the Disjoint-paths problem where the pairs are associated with ordering constraints. In our approach, we reduce ODP to the Ordered simple path with mandatory nodes problem (OSPMN), i.e., the problem of finding a simple path containing a set of mandatory nodes in a given order. The reduction of the problem is motivated by the fact that we have an appropriate way of dealing with OSPMN based on DomReachability, a propagator that implements a generalized reachability constraint on a directed graph based on the concept of graph variables. The DomReachability constraint has three arguments: (1) a flow graph, i.e., a directed graph with a source node; (2) the dominance relation graph on nodes and edges of the flow graph; and (3) the transitive closure of the flow graph. Our experimental evaluation of DomReachability shows that it provides strong pruning, obtaining solutions with very little search. Furthermore, we show that DomReachability is also useful for defining a good labeling strategy. These experimental results give evidence that DomReachability is a useful primitive for solving constrained path problems over directed graphs. We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds @math on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a @math -approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex @math is at most @math . This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly @math -Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost @math -edge-connected subgraph with at least @math vertices, which we call the @math -subgraph problem. This generalizes some well-studied classical problems such as the @math -MST and the minimum cost @math -edge-connected subgraph problems. We give a polylogarithmic approximation for the @math -subgraph problem. However, by relating it to the Densest @math -Subgraph problem, we provide evidence that the @math -subgraph problem might be hard to approximate for arbitrary @math . The paper introduces the MST(G,T,W) constraint, which is specified on two graph variables G and T and a vector W of scalar variables. The constraint is satisfied if T is a minimum spanning tree of G, where the edge weights are specified by the entries of W. We develop algorithms that filter the domains of all variables to bound consistency. We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of α per edge. The goal of every player is to minimize the sum consisting of (a) the cost of the links he has created and (b) the sum of the distances to all other players. conjectured that there exists a constant A such that, for any α > A, all non-transient Nash equilibria graphs are trees. They showed that if a Nash equilibrium is a tree, the price of anarchy is constant. In this paper we disprove the tree conjecture. More precisely, we show that for any positive integer n 0 , there exists a graph built by n ≥ n 0 players which contains cycles and forms a non-transient Nash equilibrium, for any α with 1 < α ≤ √n 2. Our construction makes use of some interesting results on finite affine planes. On the other hand we show that, for α ≥ 12n[log n], every Nash equilibrium forms a tree.Without relying on the tree conjecture, proved an upper bound on the price of anarchy of O(√α), where α ∈ [2, n2]. We improve this bound. Specifically, we derive a constant upper bound for α ∈ O(√n) and for α ≥ 12n[log n]. For the intermediate values we derive an improved bound of O(1 + (min α2 n, n2 α )1 3).Additionally, we develop characterizations of Nash equilibria and extend our results to a weighted network creation game as well as to scenarios with cost sharing. The capacity of an arbitrary ad-hoc network is difficult to estimate due to interference between the links. We use a conflict graph that models this interference relationship to determine if a set of flow rates can be accommodated. Using the cliques (complete subgraphs) of the conflict graph, we derive constraints that are sufficient for a set of flow rates to be feasible, yet are guaranteed to be within a constant bound of the optimal. We also compute an alternate set of sufficient constraints that can be easily derived from the rows of the matrix representation of the conflict graph. These two sets of constraints are particularly useful because their construction and verification may be distributed across the nodes of a network. We also extend the ad-hoc network model to incorporate variations in the interference range, and obstructions in the network. In this paper, we consider the classical contention resolution problem in which an unknown subset of n possible nodes are activated and connected to a shared channel. The problem is solved in the first round that an active node transmits alone (thus breaking symmetry). Contention resolution has been an active research topic for over four decades. Accordingly, tight upper and lower bounds are known for most major model assumptions. There remains, however, an important case that is unresolved: contention resolution with multiple channels and collision detection. (Tight bounds are known for contention resolution with multiple channels, and contention resolution with collision detection, but not for the combination of both assumptions.) Recent work proved the first non-trivial lower bound for randomized solutions to this problem in this setting. The optimality of this lower bound was left an open question. In this paper, we answer this open question by describing and analyzing new contention resolution algorithms that match, or come within a log factor of matching, this bound for all relevant parameters. By doing so, we help advance our understanding of an important longstanding problem. Of equal importance, our solutions introduce a novel new technique in which we leverage a distributed structure we call coalescing cohorts to simulate a well-known parallel search strategy from the structured PRAM CREW model in our unstructured distributed model. We conjecture that this approach is relevant to many problems in the increasingly important setting of distributed computation using multiple shared channels. A network interdiction problem usually involves two players who compete in a min‐max or max‐min game. One player, the network owner, tries to optimize its objective over the network, for example, as measured by a shortest path, maximum flow, or minimum cost flow. The opposing player, called the interdictor, alters the owner’s network to maximally impair the owner’s objective (e.g., by destroying arcs that maximize the owner’s shortest path). This chapter LetH=(T,U) be a connected graph,V?Ta set, andca non-negative function on the unordered pairs of elements ofV. In theminimum0-extension problem(*), one is asked to minimize the inner productcmover all metricsmonVsuch that (i)mcoincides with the distance function ofHwithinT; and (ii) eachv?Vis at zero distance from somes?T, i.e.m(v,s)=0. This problem is known to be NP-hard ifH=K3(as being equivalent to the minimum 3-terminal cut problem), while it is polynomially solvable ifH=K2(the minimum cut problem) orH=K2,r(the minimum (2,r)-metric problem). We study problem (*) for all fixedH. More precisely, we consider the linear programming relaxation (**) of (*) that is obtained by dropping condition (ii) above, and callHminimizableif the minima in (*) and (**) coincide for allVandc. Note that for such anHproblem (*) is solvable in strongly polynomial time. Our main theorem asserts thatHis minimizable if and only ifHis bipartite, has no isometric circuit with six or more nodes, and is orientable in the sense thatHcan be oriented so that nonadjacent edges of any 4-circuit are oppositely directed along this circuit. The proof is based on a combinatorial and topological study of tight and extreme extensions of graph metrics. Based on the idea of the proof of the NP-hardness for the minimum 3-terminal cut problem in 4, we then show that the minimum 0-extension problem is strongly NP-hard for many non-minimizable graphsH. Other results are also presented. The well-known @math -disjoint path problem ( @math -DPP) asks for pairwise vertex-disjoint paths between @math specified pairs of vertices @math in a given graph, if they exist. The decision version of the shortest @math -DPP asks for the length of the shortest (in terms of total length) such paths. Similarly the search and counting versions ask for one such and the number of such shortest set of paths, respectively. We restrict attention to the shortest @math -DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdiere and Schrijver for the general one-face problem. We do so by providing a randomised @math algorithm along with an @math time randomised sequential algorithm. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals. In addition, the earlier best known sequential algorithms (e.g. ) were randomised while ours are also deterministic. The algorithms are based on a bijection between a shortest @math -tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "good" cycle covers. The dispersion problem arises in selecting facilities to maximize some function of the distances between the facilities. The problem also arises in selecting nondominated solutions for multiobjective decision making. It is known to be NP-hard under two objectives: maximizing the minimum distance (MAX-MIN) between any pair of facilities and maximizing the average distance (MAX-AVG). We consider the question of obtaining near-optimal solutions. for MAX-MIN, we show that if the distances do not satisfy the triangle inequality, there is no polynomial-time relative approximation algorithm unless P = NP. When the distances satisfy the triangle inequality, we analyze an efficient heuristic and show that it provides a performance guarantee of two. We also prove that obtaining a performance guarantee of less than two is NP-hard. for MAX-AVG, we analyze an efficient heuristic and show that it provides a performance guarantee of four when the distances satisfy the triangle inequality. We also present a polynomial-ti...