ﻻ يوجد ملخص باللغة العربية
We study the complexity of approximating the vertex expansion of graphs $G = (V,E)$, defined as [ Phi^V := min_{S subset V} n cdot frac{|N(S)|}{|S| |V backslash S|}. ] We give a simple polynomial-time algorithm for finding a subset with vertex expansion $O(sqrt{OPT log d})$ where $d$ is the maximum degree of the graph. Our main result is an asymptotically matching lower bound: under the Small Set Expansion (SSE) hypothesis, it is hard to find a subset with expansion less than $Csqrt{OPT log d}$ for an absolute constant $C$. In particular, this implies for all constant $epsilon > 0$, it is SSE-hard to distinguish whether the vertex expansion $< epsilon$ or at least an absolute constant. The analogous threshold for edge expansion is $sqrt{OPT}$ with no dependence on the degree; thus our results suggest that vertex expansion is harder to approximate than edge expansion. In particular, while Cheegers algorithm can certify constant edge expansion, it is SSE-hard to certify constant vertex expansion in graphs. Our proof is via a reduction from the {it Unique Games} instance obtained from the SSE hypothesis to the vertex expansion problem. It involves the definition of a smoother intermediate problem we call {sf Analytic Vertex Expansion} which is representative of both the vertex expansion and the conductance of the graph. Both reductions (from the UGC instance to this problem and from this problem to vertex expansion) use novel proof ideas.
Bobkov, Houdre, and the last author introduced a Poincare-type functional parameter, $lambda_infty$, of a graph $G$. They related $lambda_infty$ to the {em vertex expansion} of the graph via a Cheeger-type inequality, analogous to the inequality rela
We study the NP-hard textsc{$k$-Sparsest Cut} problem ($k$SC) in which, given an undirected graph $G = (V, E)$ and a parameter $k$, the objective is to partition vertex set into $k$ subsets whose maximum edge expansion is minimized. Herein, the edge
We propose models for lobbying in a probabilistic environment, in which an actor (called The Lobby) seeks to influence voters preferences of voting for or against multiple issues when the voters preferences are represented in terms of probabilities.
Rummikub is a tile-based game in which each player starts with a hand of $14$ tiles. A tile has a value and a suit. The players form sets consisting of tiles with the same suit and consecutive values (runs) or tiles with the same value and different
In two papers, Burgisser and Ikenmeyer (STOC 2011, STOC 2013) used an adaption of the geometric complexity theory (GCT) approach by Mulmuley and Sohoni (Siam J Comput 2001, 2008) to prove lower bounds on the border rank of the matrix multiplication t