Given an n-point metric space (X,d_X), a tree cover 𝒯 is a set of |𝒯| = k trees on X such that every pair of vertices in X has a low-distortion path in one of the trees in 𝒯. Tree covers have been playing a crucial role in graph algorithms for decades, and the research focus is the construction of tree covers with small size k and distortion. When k = 1, the best distortion is known to be Θ(n). For a constant k ≥ 2, the best distortion upper bound is Õ(n^{1/k}) and the strongest lower bound is Ω(log_k n), leaving a gap to be closed. In this paper, we improve the lower bound to Ω(n^{1/(2^{k-1)}}). Our proof is a novel analysis on a structurally simple grid-like graph, which utilizes some combinatorial fixed-point theorems. We believe that they will prove useful for analyzing other tree-like data structures as well.

Federated Graph Learning (FGL) has emerged as a compelling paradigm for distributed Graph Neural Networks (GNNs) training, prioritizing data privacy preservation. However, due to the limitations of data collection and storage conditions, FGL suffers from data corruption in real-world applications. While Federated Learning (FL) and FGL studies have addressed label corruption, the challenge of graph topological corruption remains unexamined. Specifically, this phenomenon significantly disrupts node connectivity patterns of graphs, leading GNNs to adopt flawed feature propagation paradigms. Existing methods with poor robustness are inevitably constrained due to the absence of targeted strategies for addressing the issues of global contaminated collaboration and local vulnerability. To tackle this challenge, we conduct the first comprehensive investigation of robust FGL against topological corruption and propose FedPRE. It comprises: (1) Feature Propagation Robustness Evaluation (FPRE), which evaluates client GNNs feature propagation robustness and adjusts their contribution during aggregation. (2) Topological Corruption-Resistant Enhancement (TCRE), which enhances robustness against corruption during local training. Extensive experiments validate the robustness and effectiveness of FedPRE against topological corruption. The code is available at https://github.com/OakleyTan/FedPRE.

Given a large graph G with a set of its k vertices called terminals, a quality-q flow sparsifier is a small graph G′ that contains the terminals and preserves all multicommodity flows between them up to some multiplicative factor q≥ 1, called the quality. Constructing flow sparsifiers with good quality and small size (|V(G′)|) has been a central problem in graph compression.

Abstract. Given an [Formula: see text]-point metric space [Formula: see text], a tree cover [Formula: see text] is a set of [Formula: see text] trees on [Formula: see text] such that every pair of vertices in [Formula: see text] has a low-distortion path in one of the trees in [Formula: see text]. Tree covers have been playing a crucial role in graph algorithms for decades, and the research focus is the construction of tree covers with small size [Formula: see text] and distortion. When [Formula: see text], the best distortion is known to be [Formula: see text]. For a constant [Formula: see text], the best distortion upper bound is [Formula: see text] and the strongest lower bound is [Formula: see text], leaving a gap to be closed. In this paper, we improve the lower bound to [Formula: see text]. Our proof is a novel analysis on a structurally simple grid-like graph, which utilizes some combinatorial fixed-point theorems. We believe that they will prove useful for analyzing other tree-like data structures as well.

Federated Graph Learning (FGL) has emerged as a solution to address real-world privacy concerns and data silos in graph learning, which relies on Graph Neural Networks (GNNs). Nevertheless, the homophily level discrepancies within the local graph data of clients, termed homophily heterogeneity, significantly degrade the generalizability of a global GNN. Existing research ignores this issue and suffers from unpromising collaboration. In this paper, we propose FedSPA, an effective framework that addresses homophily heterogeneity from the perspectives of homophily conflict and homophily bias. In the first place, the homophily conflict arises when training on inconsistent homophily levels across clients. Correspondingly, we propose Subgraph Feature Propagation Decoupling (SFPD), thereby achieving collaboration on unified homophily levels across clients. To further address homophily bias, we design Homophily Bias-Driven Aggregation (HBDA) which emphasizes clients with lower biases. It enables the adaptive adjustment of each client contribution to the global GNN based on its homophily bias. The superiority of FedSPA is validated through extensive experiments. The code is available at https://github.com/OakleyTan/FedSPA.

We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with k terminals, the goal is to construct an emulator, which is a smaller edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct exact planar emulators of size $O\left(f^{2} k^{2}\right)$ in the setting where terminals lie on f faces in the planar embedding of the input graph. Our result generalizes and interpolates between the previous results of Chang and Ophelders and Goranci, Henzinger, and Peng which is an $O\left(k^{2}\right)$ bound in the setting where all terminals lie on a single face (i.e., f = 1), and the result of Krauthgamer, Nguyen, and Zondiner, which is an $O\left(k^{4}\right)$ bound for the general case (i.e., f=k).Our construction follows a recent new way of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

We study vertex sparsification for preserving cuts. Given a graph G with a subset |T| = k of its vertices called terminals, a quality-q cut sparsifier is a graph G' that contains T, such that, for any partition (T₁,T₂) of T into non-empty subsets, the value of the min-cut in G' separating T₁ from T₂ is within factor q from the value of the min-cut in G separating T₁ from T₂. The construction of cut sparsifiers with good (small) quality and size has been a central problem in graph compression for years. Planar graphs and quasi-bipartite graphs are two important special families studied in this research direction. The main results in this paper are new cut sparsifier constructions for them in the high-quality regime (where q = 1 or 1+{ε} for small {ε} > 0). We first show that every planar graph admits a planar quality-(1+{ε}) cut sparsifier of size Õ(k/poly({ε})), which is in sharp contrast with the lower bound of 2^{Ω(k)} for the quality-1 case. We then show that every quasi-bipartite graph admits a quality-1 cut sparsifier of size 2^{Õ(k²)}. This is the second to improve over the doubly-exponential bound for general graphs (previously only planar graphs have been shown to have single-exponential size quality-1 cut sparsifiers). Lastly, we show that contraction, a common approach for constructing cut sparsifiers adopted in most previous works, does not always give optimal bounds for cut sparsifiers. We demonstrate this by showing that the optimal size bound for quality-(1+{ε}) contraction-based cut sparsifiers for quasi-bipartite graphs lies in the range [k^{̃Ω(1/{ε})},k^{O(1/{ε}²)}], while in previous work an upper bound of Õ(k/{ε}²) was achieved via a non-contraction approach.

Federated Graph Learning (FGL) combines the privacy-preserving capabilities of Federated Learning (FL) with the strong graph modeling capability of Graph Neural Networks (GNNs). Current research addresses subgraph-FL from the structural perspective, neglecting the propagation of graph signals on the spatial and spectral domains of the structure. From a spatial perspective, subgraph-FL introduces edge disconnections between clients, leading to disruptions in label signals and a degradation in the semantic knowledge of the global GNN. From a spectral perspective, spectral heterogeneity causes inconsistencies in signal frequencies across subgraphs, which makes local GNNs overfit the local signal propagation schemes. As a result, spectral client drift occurs, undermining global generalizability. To tackle the challenges, we propose a global knowledge repository to mitigate the challenge of poor semantic knowledge caused by label signal disruption. Furthermore, we design a frequency alignment to address spectral client drift. The combination of Spatial and Spectral strategies forms our framework $S^2$FGL. Extensive experiments on multiple datasets demonstrate the superiority of $S^2$FGL. The code is available at https://github.com/Wonder7racer/S2FGL.git.

In the well-studied metric distortion problem in social choice, we have voters and candidates located in a shared metric space, and the objective is to design a voting rule that selects a candidate with minimal total distance to the voters. However, the voting rule has limited information about the distances in the metric, such as each voter's ordinal rankings of the candidates in order of distances. The central question is whether we can design rules that, for any election and underlying metric space, select a candidate whose total cost deviates from the optimal by only a small factor, referred to as the distortion.

We study the following distance realization problem. Given a quasi-metric D on a set T of terminals, does there exist a directed Okamura-Seymour graph that realizes D as the (directed) shortest-path distance metric on T? We show that, if we are further given the circular ordering of terminals lying on the boundary, then Monge property is a sufficient and necessary condition. This generalizes previous results for undirected Okamura-Seymour instances.

Expander decompositions form the basis of one of the most flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander de-compositions generalize this paradigm to better work for problems with lengths, distances and costs. Roughly, an$(h,s)$-length$\phi$-expander decomposition is a small collection of length increases to a graph so that nodes within distance$h$can route flow over paths of length$hs$with congestion at most$1/\phi$. In this work, we give a close-to-linear time algorithm for computing length-constrained expander decompositions in graphs with general lengths and capacities. Notably, and unlike previous works, our algorithm allows for one to trade off off between the size of the decomposition and the length of routing paths: for any$\epsilon > 0$not too small, our algorithm computes in close-to-linear time an$(h, s)$-length$\phi$-expander decomposition of size$m\cdot\phi\cdot n^{\epsilon}$where$s$= exp(poly$(1/\epsilon)$). The key foundations of our algorithm are: (1) a simple yet powerful structural theorem which states that the union of a sequence of sparse length-constrained cuts is itself sparse and (2) new algorithms for efficiently computing sparse length-constrained flows.

Personalized Federated Graph Learning (pFGL) facilitates the decentralized training of Graph Neural Networks (GNNs) without compromising privacy while accommodating personalized requirements for non-IID participants. In cross-domain scenarios, structural heterogeneity poses significant challenges for pFGL. Nevertheless, previous pFGL methods incorrectly share non-generic knowledge globally and fail to tailor personalized solutions locally under domain structural shift. We innovatively reveal that the spectral nature of graphs can well reflect inherent domain structural shifts. Correspondingly, our method overcomes it by sharing generic spectral knowledge. Moreover, we indicate the biased message-passing schemes for graph structures and propose the personalized preference module. Combining both strategies, we propose our pFGL framework $\textbf{FedSSP}$ which $\textbf{S}$hares generic $\textbf{S}$pectral knowledge while satisfying graph $\textbf{P}$references. Furthermore, We perform extensive experiments on cross-dataset and cross-domain settings to demonstrate the superiority of our framework. The code is available at https://github.com/OakleyTan/FedSSP.

In the Steiner point removal (SPR) problem, we are given a (weighted) graph G and a subset T of its vertices called terminals, and the goal is to compute a (weighted) graph H on T that is a minor of G, such that the distance between every pair of terminals is preserved to within some small multiplicative factor, that is called the stretch of H.

Given a large graph G with a subset |T| = k of its vertices called terminals, a quality-q flow sparsifier is a small graph G’ that contains T and preserves all multicommodity flows that can be routed between terminals in T, to within factor q. The problem of constructing flow sparsifiers with good (small) quality and (small) size has been a central problem in graph compression for decades.

We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP) tour in a metric on n points. We start by exploring this estimation task in the regime of o(n) space, when the input is presented as a stream of all binom(n,2) entries of the metric in an arbitrary order (a metric stream). For any α ≥ 2, we show that both MST and TSP cost can be α-approximated using Õ(n/α) space, and moreover, Ω(n/α²) space is necessary for this task. We further show that even if the streaming algorithm is allowed p passes over a metric stream, it still requires Ω̃(√{n/α p²}) space. We next consider the well-studied semi-streaming regime. In this regime, it is straightforward to compute MST cost exactly even in the case where the input stream only contains the edges of a weighted graph that induce the underlying metric (a graph stream), and the main challenging problem is to estimate TSP cost to within a factor that is strictly better than 2. We show that in graph streams, for any ε > 0, any one-pass (2-ε)-approximation of TSP cost requires Ω(ε² n²) space. On the other hand, we show that there is an Õ(n) space two-pass algorithm that approximates the TSP cost to within a factor of 1.96. Finally, we consider the query complexity of estimating metric TSP cost to within a factor that is strictly better than 2 when the algorithm is given access to an n × n matrix that specifies pairwise distances between n points. The problem of MST cost estimation in this model is well-understood and a (1+ε)-approximation is achievable by Õ(n/ε^{O(1)}) queries. However, for estimating TSP cost, it is known that an analogous result requires Ω(n²) queries even for (1,2)-TSP, and for general metrics, no algorithm that achieves a better than 2-approximation with o(n²) queries is known. We make progress on this task by designing an algorithm that performs Õ(n^{1.5}) distance queries and achieves a strictly better than 2-approximation when either the metric is known to contain a spanning tree supported on weight-1 edges or the algorithm is given access to a minimum spanning tree of the graph. Prior to our work, such results were only known for the special cases of graphic TSP and (1,2)-TSP. In terms of techniques, our algorithms for metric TSP cost estimation in both streaming and query settings rely on estimating the cover advantage which intuitively measures the cost needed to turn an MST into an Eulerian graph. One of our main algorithmic contributions is to show that this quantity can be meaningfully estimated by a sublinear number of queries in the query model. On one hand, the fact that a metric stream reveals pairwise distances for all pairs of vertices provably helps algorithmically. On the other hand, it also seems to render useless techniques for proving space lower bounds via reductions from well-known hard communication problems. Our main technical contribution in lower bounds is to identify and characterize the communication complexity of new problems that can serve as canonical starting point for proving metric stream lower bounds.

We propose a new conjecture on hardness of 2-CSP’s, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a variation of the Graph Crossing Number problem, follow from this conjecture. The conjecture can be viewed as occupying a middle ground between the d-to-1 conjecture, and hardness results for 2-CSP’s that can be obtained via standard techniques, such as Parallel Repetition combined with standard 2-prover protocols for the 3SAT problem. We hope that this work will motivate further exploration of hardness of 2-CSP’s in the regimes arising from the conjecture. We believe that a positive resolution of the conjecture will provide a good starting point for other hardness of approximation proofs. Another contribution of our work is proving that the problems that we consider are roughly equivalent from the approximation perspective. Some of these problems arose in previous work, from which it appeared that they may be related to each other. We formalize this relationship in this work.

In the metric Steiner Tree problem, we are given an n × n metric w on a set V of vertices along with a set T ⊆ V of k terminals, and the goal is to find a tree of minimum cost that contains all terminals in T. This is a well-known NP-hard problem and much of the previous work has focused on understanding its polynomial-time approximability. In this work, we initiate a study of the query complexity of the metric Steiner Tree problem. Specifically, if we desire an α-approximate estimate of the metric Steiner Tree cost, how many entries need to be queried in the metric w? For the related minimum spanning tree (MST) problem, this question is well-understood. For any fixed ε > 0, one can estimate the MST cost to within a (1 + ε)-factor using only Õ(n) queries, and this is known to be essentially tight. Can one obtain a similar result for Steiner Tree cost? Note that a (2 + ε)-approximate estimate of Steiner Tree cost can be obtained with Õ(k) queries by simply applying the MST cost estimation algorithm on the metric induced by the terminals. Our first result shows that the Steiner Tree problem behaves in a fundamentally different manner from MST: any (randomized) algorithm that estimates the Steiner Tree cost to within a (5/3 — ε)-factor requires Ω(n2) queries, even if k is a constant. This lower bound is in sharp contrast to an upper bound of O(nk) queries for computing a (5/3)-approximate Steiner Tree, which follows from previous work by Du and Zelikovsky. Our second main result, and the main technical contribution of this work, is a sublinear query algorithm for estimating the Steiner Tree cost to within a strictly better-than-2 factor. We give an algorithm that achieves this goal, with a query complexity of Õ(n12/7 + n6/7 · k); since k ≤ n, the algorithm performs at most O(n13/7) = o(n2) queries in the worst-case. Our estimation algorithm reduces this task to that of designing a sublinear query algorithm for a suitable set cover problem. We complement this result by showing an query lower bound for any algorithm that estimates Steiner Tree cost to a strictly better than 2 factor. Thus queries are needed to just beat 2-approximation when k = Ω(n); a sharp contrast to MST cost estimation where a (1 + o(1))-approximate estimate of cost is achievable with only Õ(n) queries. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.03893

Given an undirected unweighted graph G = (V, E) on n vertices and m edges, a subgraph H⊆ G is a spanner of G with stretch function f: ℝ+ → ℝ+, iff for every pair s, t of vertices in V, distH(s, t)≤ f(distG(s, t)). When f(d) = d + o(d), H is called a sublinear additive spanner; when f(d) = d + o(n), H is called an additive spanner, and f(d) − d is usually called the additive stretch of H.

We study the worst-case welfare of item pricing in the tollbooth problem. The problem was first introduced by Guruswami et al. [27], and is a special case of the combinatorial auction in which (i) each of the m items in the auction is an edge of some underlying graph; and (ii) each of the n buyers is single-minded and only interested in buying all edges of a single path. We consider the competitive ratio between the hindsight optimal welfare and the optimal worst-case welfare among all item-pricing mechanisms, when the order of the arriving buyers is adversarial. We assume that buyers own the tie-breaking power, i.e. they can choose whether or not to buy the demand path at 0 utility. We prove a tight competitive ratio of 3/2 when the underlying graph is a single path (also known as the highway problem), whereas item-pricing can achieve the hindsight optimal if the seller is allowed to choose a proper tie-breaking rule to maximize the welfare [6, 11]. Moreover, we prove an O(1) upper bound of competitive ratio when the underlying graph is a tree.

We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph G (with edge weights) and a subset of k terminal vertices, the goal is to construct an ε-emulator, which is a small planar graph G′ that contains the terminals and preserves the distances between the terminals up to factor 1+ε.

We consider the classical Minimum Crossing Number problem: given an n-vertex graph G, compute a drawing of G in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on Δ – the maximum vertex degree in G. The best current approximation algorithm achieves an O(n1/2−· (Δ·logn))-approximation, for a small fixed constant є, while the best negative result is APX-hardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomized O(2O((logn)7/8loglogn)·(Δ))-approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial in n approximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial in n).

We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with n vertices undergoing edge insertions and deletions using no(1) update time. An expander hierarchy is a tree representation of graphs that faithfully captures the cut-flow structure and consequently our dynamic algorithm almost immediately implies several results including: The first fully dynamic algorithm with no(1) worst-case update time that allows querying no(1)-approximate conductance, s-t maximum flows, and s-t minimum cuts for any given (s, t) in O(log1/6 n) time. Our results are deterministic and extend to multi-commodity cuts and flows. All previous fully dynamic (or even decremental) algorithms for any of these problems take Ω(n) update or query time. The key idea behind these results is a fully dynamic algorithm for maintaining a tree flow sparsifier, a notion introduced by Räcke [FOCS'02] for constructing competitive oblivious routing schemes. A deterministic fully dynamic connectivity algorithm with no(1) worst-case update time. This significantly simplifies the recent algorithm by Chuzhoy et al. that uses the framework of Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17]. A deterministic fully dynamic treewidth decomposition algorithm on constant-degree graphs with no(1) worst-case update time that maintains a treewidth decomposition of width tw(G) · no(1) where tw(G) denotes the treewidth of the current graph. This is the first non-trivial dynamic algorithm for this problem. Our technique is based on a new stronger notion of the expander decomposition, called the boundary-linked expander decomposition. This decomposition is more robust against updates and better captures clustering structure of graphs compared to the standard expander decomposition. Given that the expander decomposition has proved extremely useful in many fields, including approximation, sketching, distributed, and dynamic algorithms, we expect that our new notion will find more future applications.

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph G in the plane so as to minimize the number of crossings between the images of its edges. The problem is notoriously difficult, and despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a Õ̃(√n)-approximation, while the best current negative results do not rule out constantfactor approximation. All current approximation algorithms for the problem build on the same paradigm, which is also used in practice: compute a set E' of edges (called a planarizing set) such that G \ E' is planar; compute a planar drawing of G\E'; then add the drawings of the edges of E' to the resulting drawing. Unfortunately, there are examples of graphs G, in which any implementation of this method must incur Ω(OPT2) crossings, where OPT is the value of the optimal solution. This barrier seems to doom the only currently known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than O(√n)-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm, that, given a bounded-degree graph G and a planarizing set E' of its edges, computes another planarizing edge set E'' with E' ⊆ E'', such that |E''| is relatively small, and there exists a nearoptimal drawing of G in which no edges of G \ E'' participate in crossings. This allows us to reduce the Crossing Number problem to Crossing Number with Rotation System - a variant of the Crossing Number problem, in which the ordering of the edges incident to every vertex is fixed as part of input. In our reduction, we obtain an instance G' of this problem, where |E(G')| is roughly bounded by the crossing number of the original graph G. We show a randomized algorithm for this new problem, that allows us to obtain an O(n1/2-ε)approximation for Graph Crossing Number on bounded-degree graphs, for some constant ε > 0.

Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every k-edge connected graph G contains a collection 𝒯 of ⌊k/2⌋ edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing 𝒯 is the largest diameter of any tree in 𝒯. A desirable property of a tree packing for leveraging the high connectivity of a graph in distributed communication networks, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing of a low-diameter graph G, whose diameter is sublinear in |V(G)|, or, alternatively, how to show that such a packing does not exist. In this paper, we provide first non-trivial upper and lower bounds on the diameter of tree packing. We start by showing that, for every k-edge connected n-vertex graph G of diameter D, there is a tree packing 𝒯 containing Ω(k) trees, of diameter O((101k log n)^D), with edge-congestion at most 2. Karger’s edge sampling technique demonstrates that, if G is a k-edge connected graph, and G[p] is a subgraph of G obtained by sampling each edge of G independently with probability p = Θ(log n/k), then with high probability G[p] is connected. We extend this result to show that the diameter of G[p] is bounded by O(k^(D(D+1)/2)) with high probability. This immediately gives a tree packing of Ω(k/log n) edge-disjoint trees of diameter at most O(k^(D(D+1)/2)). We also show that these two results are nearly tight for graphs with a small diameter: we show that there are k-edge connected graphs of diameter 2D, such that any packing of k/α trees with edge-congestion η contains at least one tree of diameter Ω((k/(2α η D))^D), for any k,α and η. Additionally, we show that if, for every pair u,v of vertices of a given graph G, there is a collection of k edge-disjoint paths connecting u to v, of length at most D each, then we can efficiently compute a tree packing of size k, diameter O(D log n), and edge-congestion O(log n). Finally, we provide several applications of low-diameter tree packing in the distributed settings of network optimization and secure computation.

This note is an erratum for the paper On the Inequalities of Projected Volumes and the Constructible Region [ SIAM J. Discrete Math., 33 (2019), pp. 694--711]. There is a mistake in the proof of Theorem 4 in Section 3. However, Theorem 4 is itself correct (a proof can be found in [ Inequalities on Projected Volumes, arxiv.org/abs/1909.12858, 2019] by Leader, Randelović, and Räty), and all the other results of the paper stand.

We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function f : ℤ+ → ℤ+, such that for every integer g > 0, every graph of treewidth at least f(g) contains the (g × g)-grid as a minor. For every integer g > 0, let f(g) be the smallest value for which the theorem holds. Establishing tight bounds on f(g) is an important graph-theoretic question. Robertson and Seymour showed that f(g) = Ω(g2 log g) must hold. For a long time, the best known upper bounds on f(g) were super-exponential in g. The first polynomial upper bound of f(g) = O(g98 poly log g) was proved by Chekuri and Chuzhoy. It was later improved to f(g) = O(g36 poly log g), and then to f(g) = O(g19 poly log g). In this paper we further improve this bound to f(g) = O(g9 poly log g). We believe that our proof is significantly simpler than the proofs of the previous bounds. Moreover, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this paper can lead to even tighter bounds on f(g).

We study the following geometry problem: given a $2^n-1$ dimensional vector $\pi=\{\pi_S\}_{S\subseteq [n], S\ne \emptyset}$, is there an object $T\subseteq\mathbb{R}^n$ such that $\log(\mathrm{vol}(T_S))= \pi_S\,\,\forall S\subseteq [n]$, where $T_S$ is the projection of $T$ onto the subspace spanned by the axes in $S$ and $\mathrm{vol}(T_S)$ is its $|S|$-dimensional volume? If $\pi$ does correspond to an object in $\mathbb{R}^n$, we say that $\pi$ is constructible. We use $\Psi_n$ to denote the constructible region, i.e., the set of all constructible vectors in $\mathbb{R}^{2^n-1}$. In 1995, Bollobás and Thomason showed that $\Psi_n$ is contained in a polyhedral cone and defined a class of so-called uniform-cover inequalities. We propose a new set of inequalities, called nonuniform-cover inequalities, which generalizes the uniform-cover inequalities. We show that any linear inequality that all points in $\Psi_n$ satisfy must be a nonuniform-cover inequality. Based on this result and an example by Bollobás and Thomason, we show that the constructible region $\Psi_n$ is nonconvex for $n\geq 4$ and thus cannot be fully characterized by linear inequalities. We further show that some subclasses of the nonuniform-cover inequalities are not satisfied by all constructible vectors via various combinatorial constructions, which refutes a previous conjecture about $\Psi_n$. Finally, we conclude with an interesting conjecture regarding the convex hull of $\Psi_n$.

A function computation problem over a directed acyclic network has been considered in the literature, where a sink node is required to compute a target function correctly with the inputs arbitrarily generated at multiple source nodes. The network links are error free but capacity limited, and the intermediate nodes perform network coding. The computing rate of a network code is the average number of times that the target function is computed for one use of the network, i.e., each link in the network is used at most once. In the existing papers, two cut-set bounds were proposed on the computing rate. However, we in this paper show that these bounds are not valid for general network function computation problems. We analyze the reason of the invalidity and propose a general cut-set bound by using a new equivalence relation associated with the inputs of the target function. Moreover, some results in the existing papers were proved by applying the invalid upper bound. We also justify the validity of these results.

In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem --- the task of finding k seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution-dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.

We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space are assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agents do not misreport their most-preferred points. We propose a resource augmentation framework, where a truthful mechanism is evaluated by its worst-case performance on an instance with enhanced facility capacities against the optimal mechanism on the same instance with the original capacities. We study a well-known mechanism, Serial Dictatorship, and provide an exact analysis of its performance. Among other results, we prove that Serial Dictatorship has approximation ratio $$g/(g-2)$$ when the capacities are multiplied by any integer $$g \ge 3$$ . Our results suggest that even a limited augmentation of the resources can have wondrous effects on the performance of the mechanism and in particular, the approximation ratio goes to 1 as the augmentation factor becomes large. We complement our results with bounds on the approximation ratio of Random Serial Dictatorship, the randomized version of Serial Dictatorship, when there is no resource augmentation.

Function computation in directed acyclic networks is considered, where a sink node wants to compute a target function with the inputs generated at multiple source nodes. The network links are error-free but capacity-limited, and the intermediate network nodes perform network coding. The target function is required to be computed with zero error. The computing rate of a network code is measured by the average number of times that the target function can be computed for one use of the network. We propose a cut-set bound on the computing rate using an equivalence relation associated with the inputs of the target function. Our bound holds for general target functions and network topologies. We also show that our bound is tight for some special cases where the computing capacity can be characterized.