Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMinimum Stable Cut and Treewidth
76
0
0.0
(
0
)
Added by
Michael Lampis
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Michael Lampis
Ask ChatGPT about the research
No Arabic abstract
A stable cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. Equivalently, a cut is stable if all vertices have the (weighted) majority of their neighbors on the other side. In this paper we study Min Stable Cut, the problem of finding a stable cut of minimum weight, which is closely related to the Price of Anarchy of the Max Cut game. Since this problem is NP-hard, we study its complexity on graphs of low treewidth, low degree, or both. We show that the problem is weakly NP-hard on severely restricted trees, so bounding treewidth alone cannot make it tractable. We match this with a pseudo-polynomial DP algorithm running in time $(Deltacdot W)^{O(tw)}n^{O(1)}$, where $tw$ is the treewidth, $Delta$ the maximum degree, and $W$ the maximum weight. On the other hand, bounding $Delta$ is also not enough, as the problem is NP-hard for unweighted graphs of bounded degree. We therefore parameterize Min Stable Cut by both $tw+Delta$ and obtain an FPT algorithm running in time $2^{O(Delta tw)}(n+log W)^{O(1)}$. Our main result is to provide a reduction showing that both aforementioned algorithms are essentially optimal, even if we replace treewidth by pathwidth: if there exists an algorithm running in $(nW)^{o(pw)}$ or $2^{o(Delta pw)}(n+log W)^{O(1)}$, then the ETH is false. Complementing this, we show that we can obtain an FPT approximation scheme parameterized by treewidth, if we consider almost-stable solutions. Motivated by these mostly negative results, we consider Unweighted Min Stable Cut. Here our results already imply a much faster exact algorithm running in time $Delta^{O(tw)}n^{O(1)}$. We show that this is also probably essentially optimal: an algorithm running in $n^{o(pw)}$ would contradict the ETH.
rate research
Read More
The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If $G$ has $n$ vertices and edge weights at least $1$ and at most $tau$, we give a quantum algorithm to solve the minimum cut problem using $tilde O(n^{3/2}sqrt{tau})$ queries and time. Moreover, for every integer $1 le tau le n$ we give an example of a graph $G$ with edge weights $1$ and $tau$ such that solving the minimum cut problem on $G$ requires $Omega(n^{3/2}sqrt{tau})$ many queries to the adjacency matrix of $G$. These results contrast with the classical randomized case where $Omega(n^2)$ queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when $G$ has $m$ edges the classical randomized complexity of the minimum cut problem is $tilde Theta(m)$. We show that the quantum query and time complexity are $tilde O(sqrt{mntau})$ and $tilde O(sqrt{mntau} + n^{3/2})$, respectively, where again the edge weights are between $1$ and $tau$. For dense graphs we give lower bounds on the quantum query complexity of $Omega(n^{3/2})$ for $tau > 1$ and $Omega(tau n)$ for any $1 leq tau leq n$. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Kargers tree packing technique (STOC 1996).
Let $G = (V,w)$ be a weighted undirected graph with $m$ edges. The cut dimension of $G$ is the dimension of the span of the characteristic vectors of the minimum cuts of $G$, viewed as vectors in ${0,1}^m$. For every $n ge 2$ we show that the cut dimension of an $n$-vertex graph is at most $2n-3$, and construct graphs realizing this bound. The cut dimension was recently defined by Graur et al. cite{GPRW20}, who show that the maximum cut dimension of an $n$-vertex graph is a lower bound on the number of cut queries needed by a deterministic algorithm to solve the minimum cut problem on $n$-vertex graphs. For every $nge 2$, Graur et al. exhibit a graph on $n$ vertices with cut dimension at least $3n/2 -2$, giving the first lower bound larger than $n$ on the deterministic cut query complexity of computing mincut. We observe that the cut dimension is even a lower bound on the number of emph{linear} queries needed by a deterministic algorithm to solve mincut, where a linear query can ask any vector $x in mathbb{R}^{binom{n}{2}}$ and receives the answer $w^T x$. Our results thus show a lower bound of $2n-3$ on the number of linear queries needed by a deterministic algorithm to solve minimum cut on $n$-vertex graphs, and imply that one cannot show a lower bound larger than this via the cut dimension. We further introduce a generalization of the cut dimension which we call the $ell_1$-approximate cut dimension. The $ell_1$-approximate cut dimension is also a lower bound on the number of linear queries needed by a deterministic algorithm to compute minimum cut. It is always at least as large as the cut dimension, and we construct an infinite family of graphs on $n=3k+1$ vertices with $ell_1$-approximate cut dimension $2n-2$, showing that it can be strictly larger than the cut dimension.
We study a combinatorial problem called Minimum Maximal Matching, where we are asked to find in a general graph the smallest that can not be extended. We show that this problem is hard to approximate with a constant smaller than 2, assuming the Unique Games Conjecture. As a corollary we show, that Minimum Maximal Matching in bipartite graphs is hard to approximate with constant smaller than $frac{4}{3}$, with the same assumption. With a stronger variant of the Unique Games Conjecture --- that is Small Set Expansion Hypothesis --- we are able to improve the hardness result up to the factor of $frac{3}{2}$.
We give improved pseudorandom generators (PRGs) for Lipschitz functions of low-degree polynomials over the hypercube. These are functions of the form psi(P(x)), where P is a low-degree polynomial and psi is a function with small Lipschitz constant. PRGs for smooth functions of low-degree polynomials have received a lot of attention recently and play an important role in constructing PRGs for the natural class of polynomial threshold functions. In spite of the recent progress, no nontrivial PRGs were known for fooling Lipschitz functions of degree O(log n) polynomials even for constant error rate. In this work, we give the first such generator obtaining a seed-length of (log n)tilde{O}(d^2/eps^2) for fooling degree d polynomials with error eps. Previous generators had an exponential dependence on the degree. We use our PRG to get better integrality gap instances for sparsest cut, a fundamental problem in graph theory with many applications in graph optimization. We give an instance of uniform sparsest cut for which a powerful semi-definite relaxation (SDP) first introduced by Goemans and Linial and studied in the seminal work of Arora, Rao and Vazirani has an integrality gap of exp(Omega((log log n)^{1/2})). Understanding the performance of the Goemans-Linial SDP for uniform sparsest cut is an important open problem in approximation algorithms and metric embeddings and our work gives a near-exponential improvement over previous lower bounds which achieved a gap of Omega(log log n).
In this note we investigate the complexity of the Minimum Label Alignment problem and we show that such a problem is APX-hard.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
