Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Parameterized Complexity of Sparsest Cut and Small-set Expansion Problems
122
0
0.0
(
0
)
Added by
Ramin Javadi
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
Let $G$ be a graph on $n$ vertices and $mathrm{STAB}_k(G)$ be the convex hull of characteristic vectors of its independent sets of size at most $k$. We study extension complexity of $mathrm{STAB}_k(G)$ with respect to a fixed parameter $k$ (analogously to, e.g., parameterized computational complexity of problems). We show that for graphs $G$ from a class of bounded expansion it holds that $mathrm{xc}(mathrm{STAB}_k(G))leqslant mathcal{O}(f(k)cdot n)$ where the function $f$ depends only on the class. This result can be extended in a simple way to a wide range of similarly defined graph polytopes. In case of general graphs we show that there is {em no function $f$} such that, for all values of the parameter $k$ and for all graphs on $n$ vertices, the extension complexity of $mathrm{STAB}_k(G)$ is at most $f(k)cdot n^{mathcal{O}(1)}.$ While such results are not surprising since it is known that optimizing over $mathrm{STAB}_k(G)$ is $FPT$ for graphs of bounded expansion and $W[1]$-hard in general, they are also not trivial and in both cases stronger than the corresponding computational complexity results.
In this paper we study the problem of finding a small safe set $S$ in a graph $G$, i.e. a non-empty set of vertices such that no connected component of $G[S]$ is adjacent to a larger component in $G - S$. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth $pw$ and cannot be solved in time $n^{o(pw)}$ unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number $vc$ unless $mathrm{PH} = Sigma^{mathrm{p}}_{3}$, but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity $nd$, and (4) it can be solved in time $n^{f(cw)}$ for some double exponential function $f$ where $cw$ is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size.
A matching is a set of edges in a graph with no common endpoint. A matching $M$ is called acyclic if the induced subgraph on the endpoints of the edges in $M$ is acyclic. Given a graph $G$ and an integer $k$, Acyclic Matching Problem seeks for an acyclic matching of size $k$ in $G$. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs with maximum degree three and girth of arbitrary large. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter $k$. On the other hand, the problem is fixed parameter tractable with respect to $k$, for line graphs, $C_4$-free graphs and every proper minor-closed class of graphs (including bounded tree-width and planar graphs).
Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khots 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain Grassmanian agreement tester. In this work, we show that the hypothesis of Dinur et. al. follows from a conjecture we call the Inverse Shortcode Hypothesis characterizing the non-expanding sets of the degree-two shortcode graph. We also show the latter conjecture is equivalent to a characterization of the non-expanding sets in the Grassman graph, as hypothesized by a follow-up paper of Dinur et. al. (2017). Following our work, Khot, Minzer and Safra (2018) proved the Inverse Shortcode Hypothesis. Combining their proof with our result and the reduction of Dinur et. al. (2016), completes the proof of the 2 to 2 conjecture with imperfect completeness. Moreover, we believe that the shortcode graph provides a useful view of both the hypothesis and the reduction, and might be useful in extending it further.
In this work, we achieve gap amplification for the Small-Set Expansion problem. Specifically, we show that an instance of the Small-Set Expansion Problem with completeness $epsilon$ and soundness $frac{1}{2}$ is at least as difficult as Small-Set Expansion with completeness $epsilon$ and soundness $f(epsilon)$, for any function $f(epsilon)$ which grows faster than $sqrt{epsilon}$. We achieve this amplification via random walks -- our gadget is the graph with adjacency matrix corresponding to a random walk on the original graph. An interesting feature of our reduction is that unlike gap amplification via parallel repetition, the size of the instances (number of vertices) produced by the reduction remains the same.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
