Stackelberg Network Pricing Games

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m priceable edges in a graph. The other edges have a fixed cost. Based on the leader’s decision one or more followers optimize a polynomial-time solvable combinatorial minimization problem and choose a minimum cost solution satisfying their requirements based on the fixed costs and the leader’s prices. The leader receives as revenue the total amount of prices paid by the followers for priceable edges in their solutions. Our model extends several known pricing problems, including single-minded and unit-demand pricing, as well as Stackelberg pricing for certain follower problems like shortest path or minimum spanning tree. Our first main result is a tight analysis of a single-price algorithm for the single follower game, which provides a (1+ε)log?m-approximation. This can be extended to provide a (1+ε)(log?k+log?m)-approximation for the general problem and k followers. The problem is also shown to be hard to approximate within $\mathcal{O}(\log^{\varepsilon}k + \log^{\varepsilon}m)$ for some ε>0. If followers have demands, the single-price algorithm provides an $\mathcal{O}(m^{2})$ -approximation, and the problem is hard to approximate within $\mathcal{O}(m^{\epsilon})$ for some ε>0. Our second main result is a polynomial time algorithm for revenue maximization in the special case of Stackelberg bipartite vertex-cover, which is based on non-trivial max-flow and LP-duality techniques. This approach can be extended to provide constant-factor approximations for any constant number of followers.     

Algorithms for Placing Monitors in a Flow Network

In the Flow Edge-Monitor Problem, we are given an undirected graph G=(V,E), an integer k>0 and some unknown circulation ψ on G. We want to find a set of k edges in G, so that if we place k monitors on those edges to measure the flow along them, the total number of edges for which the flow can be uniquely determined is maximized. In this paper, we first show that the Flow Edge-Monitor Problem is NP-hard. Then we study an algorithm called σ-Greedy that, in each step, places monitors on σ edges for which the number of edges where the flow is determined is maximized. We show that the approximation ratio of 1-Greedy is 3 and that the approximation ratio of 2-Greedy is 2.     

The Price of Anarchy in Network Creation Games Is (Mostly) Constant

We study the price of anarchy and the structure of equilibria in network creation games. A network creation game is played by n players {1,2,…,n}, each identified with a vertex of a graph (network), where the strategy of player i, i=1,…,n, is to build some edges adjacent to i. The cost of building an edge is α>0, a fixed parameter of the game. The goal of every player is to minimize its creation cost plus its usage cost. The creation cost of player i is α times the number of built edges. In the SumGame variant, the usage cost of player i is the sum of distances from i to every node of the resulting graph. In the MaxGame variant, the usage cost is the eccentricity of i in the resulting graph of the game. In this paper we improve previously known bounds on the price of anarchy of the game (of both variants) for various ranges of α, and give new insights into the structure of equilibria for various values of α. The two main results of the paper show that for α>273?n all equilibria in SumGame are trees and thus the price of anarchy is constant, and that for α>129 all equilibria in MaxGame are trees and the price of anarchy is constant. For SumGame this answers (almost completely) one of the fundamental open problems in the field—is price of anarchy of the network creation game constant for all values of α?—in an affirmative way, up to a tiny range of α.     

Computational comparisons of different formulations for the Stackelberg minimum spanning tree game

Let be a given graph whose edge set is partitioned into a set R of red edges and a set B of blue edges, and assume that red edges are weighted and contain a spanning tree of G. Then, the Stackelberg minimum spanning tree game (StackMST) is that of pricing (i.e., weighting) the blue edges in such a way that the total weight of the blue edges selected in a minimum spanning tree of the resulting graph is maximized. In this paper, we present different new mathematical programming formulations for the StackMST based on the properties of the minimum spanning tree problem and the bilevel optimization. We establish a theoretical and empirical comparison between these new formulations that are able to solve random instances of 20–70 nodes. We also test our models on instances in the literature, outperforming previous results.     

Small Vertex Cover makes Petri Net Coverability and Boundedness Easier

The coverability and boundedness problems for Petri nets are known to be Expspace-complete. Given a Petri net, we associate a graph with it. With the vertex cover number k of this graph and the maximum arc weight W as parameters, we show that coverability and boundedness are in ParaPspace. This means that these problems can be solved in space $\mathcal{O} ({\mathit{ef}}(k, W){\mathit{poly}}(n) )$ , where ef(k,W) is some super-polynomial function and poly(n) is some polynomial in the size of the input n. We then extend the ParaPspace result to model checking a logic that can express some generalizations of coverability and boundedness.     

Detecting Fixed Patterns in Chordal Graphs in Polynomial Time

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.     

Survivable network design: the capacitated minimum spanning network problem

We are given an undirected graph G=(V,E) with positive weights on its vertices representing demands, and non-negative costs on its edges. Also given are a capacity constraint k, and root vertex r∈V. In this paper, we consider the capacitated minimum spanning network (CMSN) problem, which asks for a minimum cost spanning network such that the removal of r and its incident edges breaks the network into a number of components (groups), each of which is 2-edge-connected with a total weight of at most k. We show that the CMSN problem is NP-hard, and present a 4-approximation algorithm for graphs satisfying triangle inequality. We also show how to obtain similar approximation results for a related 2-vertex-connected CMSN problem.     

Vertex Cover Kernelization Revisited

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G′,k′) in polynomial time with the guarantee that G′ has at most 2k′ vertices (and thus $\mathcal{O}((k')^{2})$ edges) with k′≤k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Θ(k ²) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number $\mathop{\mathrm{\mbox {\textsc{vc}}}}(G)$ since $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)\leq\mathop{\mathrm{\mbox{\textsc{vc}}}}(G)$ and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ : an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G′,X′,k′) such that |V(G′)|≤2k and $|V(G')| \in\mathcal{O}(|X'|^{3})$ . A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have a polynomial kernel when parameterized by the cardinality of a given vertex cover of the graph unless NP ? coNP/poly and the polynomial hierarchy collapses to the third level.     

Approximating Node-Connectivity Augmentation Problems

We consider the (undirected) Node Connectivity Augmentation (NCA) problem: given a graph J=(V,E _J ) and connectivity requirements $\{r(u,v): u,v \in V\}$ , find a minimum size set I of new edges (any edge is allowed) such that the graph J∪I contains r(u,v) internally-disjoint uv-paths, for all u,v∈V. In Rooted NCA there is s∈V such that r(u,v)>0 implies u=s or v=s. For large values of k=max? _u,v∈V r(u,v), NCA is at least as hard to approximate as Label-Cover and thus it is unlikely to admit an approximation ratio polylogarithmic in k. Rooted NCA is at least as hard to approximate as Hitting-Set. The previously best approximation ratios for the problem were O(kln?n) for NCA and O(ln?n) for Rooted NCA. In this paper we give an approximation algorithm with ratios O(kln?² k) for NCA and O(ln?² k) for Rooted NCA. This is the first approximation algorithm with ratio independent of?n, and thus is a constant for any fixed k. Our algorithm is based on the following new structural result which is of independent interest. If $\mathcal{D}$ is a set of node pairs in a graph?J, then the maximum degree in the hypergraph formed by the inclusion minimal tight sets separating at least one pair in $\mathcal{D}$ is O(? ²), where ? is the maximum connectivity in J of a pair in $\mathcal{D}$ .     

Minimize the Maximum Duty in Multi-interface Networks

We consider devices equipped with multiple wired or wireless interfaces. By switching of various interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider two basic networking problems in the field of multi-interface networks. The first one, known as the Coverage problem, requires to establish the connections defined by a network. The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network. Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node. We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case. We prove that the Coverage problem is NP-hard for any fixed Δ≥5 and k≥16, with Δ being the maximum degree, and k being the number of different interfaces among the network. We also show that, unless P=NP, the problem cannot be approximated within a factor of ηln?Δ, for a certain constant η. We then provide a general approximation algorithm which guarantees a factor of O((1+b)ln?Δ), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented. Concerning the Connectivity problem, we prove that it is NP-hard for any fixed Δ≥3 and k≥10. Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of ηln?Δ, for a certain constant η. We then provide approximation and exact algorithms for the general problem and for special cases, respectively.     

Contracting Graphs to Paths and Trees

Vertex deletion and edge deletion problems play a central role in parameterized complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. The study of analogous edge contraction problems has so far been left largely unexplored from a parameterized perspective. We consider two basic problems of this type: Tree Contraction and Path Contraction. These two problems take as input an undirected graph G on n vertices and an integer k, and the task is to determine whether we can obtain a tree or a path, respectively, by a sequence of at most k edge contractions in G. For Tree Contraction, we present a randomized 4 ^k ? n ^O(1) time polynomial-space algorithm, as well as a deterministic 4.98 ^k ? n ^O(1) time algorithm, based on a variant of the color coding technique of Alon, Yuster and Zwick. We also present a deterministic 2 ^k+o(k)+n ^O(1) time algorithm for Path Contraction. Furthermore, we show that Path Contraction has a kernel with at most 5k+3 vertices, while Tree Contraction does not have a polynomial kernel unless NP ? coNP/poly. We find the latter result surprising because of the connection between Tree Contraction and Feedback Vertex Set, which is known to have a kernel with 4k ² vertices.     

On Cutwidth Parameterized by Vertex Cover

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 ^k n ^O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 ^n/2 n ^O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP?coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.     

A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments

In the k-Feedback Arc/Vertex Set problem we are given a directed graph D and a positive integer k and the objective is to check whether it is possible to delete at most k arcs/vertices from D to make it acyclic. Dom et al. (J. Discrete Algorithm 8(1):76–86, 2010) initiated a study of the Feedback Arc Set problem on bipartite tournaments (k-FASBT) in the realm of parameterized complexity. They showed that k-FASBT can be solved in time O(3.373 ^k n ⁶) on bipartite tournaments having n vertices. However, until now there was no known polynomial sized problem kernel for k-FASBT. In this paper we obtain a cubic vertex kernel for k-FASBT. This completes the kernelization picture for the Feedback Arc/Vertex Set problem on tournaments and bipartite tournaments, as for all other problems polynomial kernels were known before. We obtain our kernel using a non-trivial application of “independent modules” which could be of independent interest.     

gbase: an efficient analysis platform for large graphs

Graphs appear in numerous applications including cyber security, the Internet, social networks, protein networks, recommendation systems, citation networks, and many more. Graphs with millions or even billions of nodes and edges are common-place. How to store such large graphs efficiently? What are the core operations/queries on those graph? How to answer the graph queries quickly? We propose Gbase, an efficient analysis platform for large graphs. The key novelties lie in (1) our storage and compression scheme for a parallel, distributed settings and (2) the carefully chosen graph operations and their efficient implementations. We designed and implemented an instance of Gbase using Mapreduce/Hadoop. Gbase provides a parallel indexing mechanism for graph operations that both saves storage space, as well as accelerates query responses. We run numerous experiments on real and synthetic graphs, spanning billions of nodes and edges, and we show that our proposed Gbase is indeed fast, scalable, and nimble, with significant savings in space and time.     

Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class.     

Parameterized Domination in Circle Graphs

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction:

• Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution.
• Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs.
• If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely $2^{\mathcal{O}(t \cdot\frac{\log\log t}{\log t})} \cdot n^{\mathcal{O}(1)}$ , where n=|V(G)|.

     

The effect of homogeneity on the computational complexity of combinatorial data anonymization

A matrix M is said to be k-anonymous if for each row r in M there are at least k ? 1 other rows in M which are identical to r. The NP-hard k-Anonymity problem asks, given an n × m-matrix M over a fixed alphabet and an integer s > 0, whether M can be made k-anonymous by suppressing (blanking out) at most s entries. Complementing previous work, we introduce two new “data-driven” parameterizations for k-Anonymity—the number t _in of different input rows and the number t _out of different output rows—both modeling aspects of data homogeneity. We show that k-Anonymity is fixed-parameter tractable for the parameter t _in , and that it is NP-hard even for t _out = 2 and alphabet size four. Notably, our fixed-parameter tractability result implies that k-Anonymity can be solved in linear time when t _in is a constant. Our computational hardness results also extend to the related privacy problems p-Sensitivity and ?-Diversity, while our fixed-parameter tractability results extend to p-Sensitivity and the usage of domain generalization hierarchies, where the entries are replaced by more general data instead of being completely suppressed.     

Degree Constrained Node-Connectivity Problems

We consider Degree Constrained Survivable Network problems. For the directed Degree Constrained k -Edge-Outconnected Subgraph problem, we slightly improve the best known approximation ratio, by a simple proof. Our main contribution is giving a framework to handle node-connectivity degree constrained problems with the iterative rounding method. In particular, for the degree constrained versions of the Element-Connectivity Survivable Network problem on undirected graphs, and of the k -Outconnected Subgraph problem on both directed and undirected graphs, our algorithm computes a solution J of cost O(logk) times the optimal, with degrees O(2 ^k )?b(v). Similar result are obtained for the k -Connected Subgraph problem. The latter improves on the only degree approximation O(klogn)?b(v) in O(n ^k ) time on undirected graphs by Feder, Motwani, and Zhu.     

The Parameterized Complexity of Stabbing Rectangles

The NP-complete geometric covering problem Rectangle Stabbing is defined as follows: Given a set R of axis-parallel rectangles in the plane, a set L of horizontal and vertical lines in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines. While it is known that the problem can be approximated in polynomial time within a factor of two, its parameterized complexity with respect to the parameter k was open so far. Giving two fixed-parameter reductions, one from the W[1]-complete problem Multicolored Clique and one to the W[1]-complete problem Short Turing Machine Acceptance, we prove that Rectangle Stabbing is W[1]-complete with respect to the parameter k, which in particular means that there is no hope for an algorithm running in f(k)?|R∪L| ^O(1) time. Our reductions also show the W[1]-completeness of the more general problem Set Cover on instances that “almost have the consecutive-ones property”, that is, on instances whose matrix representation has at most two blocks of 1s per row. We also show that the special case of Rectangle Stabbing where all rectangles are squares of the same size is W[1]-hard. The case where the input consists of non-overlapping rectangles was open for some time and has recently been shown to be fixed-parameter tractable (Heggernes et al., Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009). By giving an algorithm running in (2k) ^k ?|R∪L| ^O(1) time, we show that Rectangle Stabbing is fixed-parameter tractable in the still NP-hard case where both these restrictions apply, that is, in the case of disjoint squares of the same size. This algorithm is faster than the one in Heggernes et al. (Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing, 2009) for the disjoint rectangles case. Moreover, we show fixed-parameter tractability for the restrictions where the rectangles have bounded width or height or where each horizontal line intersects only a bounded number of rectangles.     

Chams: Churn-aware overlay construction for media streaming

Overlay networks support a wide range of peer-to-peer media streaming applications on the Internet. The user experience of such applications is affected by the churn resilience of the system. When peers disconnect from the system, streamed data may be delayed or lost due to missing links in the overlay topology. In this paper, we explore a proactive strategy to create churn-aware overlay networks that reduce the potential of disruptions caused by churn events. We describe Chams, a middleware for constructing overlay networks that mitigates the impact of churn. Chams uses a ??hybrid?? approach??it implicitly defines an overlay topology using a gossip-style mechanism, while taking the reliability of peers into account. Unlike systems for overlay construction, Chams supports a variety of topologies used in media streaming systems, such as trees, multi-trees and forests. We evaluate Chams with different topologies and show that it reduces the impact of churn, while imposing only low computational and message overheads.