Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Complexity of Approximating Vertex Expansion
115
0
0.0
(
0
)
Added by
Anand Louis
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 relating the spectral gap of the graph, $lambda_2$, to its {em edge expansion}. While $lambda_2$ can be computed efficiently, the computational complexity of $lambda_infty$ has remained an open question. Following the work of the second author with Raghavendra and Vempala, wherein the complexity of $lambda_infty$ was related to the so-called small-set expansion (SSE) problem, it has been believed that computing $lambda_infty$ is a hard problem. We confirm this conjecture by proving that computing $lambda_infty$ is indeed NP-hard, even for weighted trees. Our gadget further proves NP-hardness of computing emph{spread constant} of a weighted tree; i.e., a geometric measure of the graph, introduced by Alon, Boppana, and Spencer, in the context of deriving an asymptotic isoperimetric inequality of Cartesian products of graphs. We conclude this case by providing a fully polynomial time approximation scheme. We further study a generalization of spread constant in machine learning literature, namely the {em maximum variance embedding} problem. For trees, we provide fast combinatorial algorithms that avoid solving a semidefinite relaxation of the problem. On the other hand, for general graphs, we propose a randomized projection method that can outperform the optimal orthogonal projection, i.e., PCA, classically used for rounding of the optimum lifted solution (to SDP relaxation) of the problem.
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 expansion of a subset $S subseteq V$ is defined as the sum of the weights of edges exiting $S$ divided by the number of vertices in $S$. Another problem that has been investigated is textsc{$k$-Small-Set Expansion} problem ($k$SSE), which aims to find a subset with minimum edge expansion with a restriction on the size of the subset. We extend previous studies on $k$SC and $k$SSE by inspecting their parameterized complexity. On the positive side, we present two FPT algorithms for both $k$SSE and 2SC problems where in the first algorithm we consider the parameter treewidth of the input graph and uses exponential space, and in the second we consider the parameter vertex cover number of the input graph and uses polynomial space. Moreover, we consider the unweighted version of the $k$SC problem where $k geq 2$ is fixed and proposed two FPT algorithms with parameters treewidth and vertex cover number of the input graph. We also propose a randomized FPT algorithm for $k$SSE when parameterized by $k$ and the maximum degree of the input graph combined. Its derandomization is done efficiently. oindent On the negative side, first we prove that for every fixed integer $k,taugeq 3$, the problem $k$SC is NP-hard for graphs with vertex cover number at most $tau$. We also show that $k$SC is W[1]-hard when parameterized by the treewidth of the input graph and the number~$k$ of components combined using a reduction from textsc{Unary Bin Packing}. Furthermore, we prove that $k$SC remains NP-hard for graphs with maximum degree three and also graphs with degeneracy two. Finally, we prove that the unweighted $k$SSE is W[1]-hard for the parameter $k$.
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. In particular, we provide two evaluation criteria and two bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria and on various natural parameterizations. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide approximability and inapproximability results for these problems and several variants.
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 suits (groups). The corresponding optimization problem is, given a hand of tiles, to form valid sets such that the score (sum of tile values) is maximized. We first present an algorithm that solves this problem in polynomial time. Next, we analyze the impact on the computational complexity when we generalize over various input parameters. Finally, we attempt to better understand some aspects involved in human play by means of an experiment that considers counting problems related to the number of possible immediately winning hands.
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 tensor. A key ingredient was information about certain Kronecker coefficients. While tensors are an interesting test bed for GCT ideas, the far-away goal is the separation of algebraic complexity classes. The role of the Kronecker coefficients in that setting is taken by the so-called plethysm coefficients: These are the multiplicities in the coordinate rings of spaces of polynomials. Even though several hardness results for Kronecker coefficients are known, there are almost no results about the complexity of computing the plethysm coefficients or even deciding their positivity. In this paper we show that deciding positivity of plethysm coefficients is NP-hard, and that computing plethysm coefficients is #P-hard. In fact, both problems remain hard even if the inner parameter of the plethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fixed, then the plethysm coefficient can be computed in polynomial time. Moreover, we derive new lower and upper bounds and in special cases even combinatorial descriptions for plethysm coefficients, which we consider to be of independent interest. Our technique uses discrete tomography in a more refined way than the recent work on Kronecker coefficients by Ikenmeyer, Mulmuley, and Walter (Comput Compl 2017). This makes our work the first to apply techniques from discrete tomography to the study of plethysm coefficients. Quite surprisingly, that interpretation also leads to new equalities between certain plethysm coefficients and Kronecker coefficients.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
