Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userParameterized Inapproximability of Target Set Selection and Generalizations
145
0
0.0
(
0
)
Added by
Florian Sikora
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value $thr(v)$ for any vertex $v$ of the graph, find a minimum size vertex-subset to activate s.t. all the vertices of the graph are activated at the end of the propagation process. A vertex $v$ is activated during the propagation process if at least $thr(v)$ of its neighbors are activated. This problem models several practical issues like faults in distributed networks or word-to-mouth recommendations in social networks. We show that for any functions $f$ and $rho$ this problem cannot be approximated within a factor of $rho(k)$ in $f(k) cdot n^{O(1)}$ time, unless FPT = W[P], even for restricted thresholds (namely constant and majority thresholds). We also study the cardinality constraint maximization and minimizati
rate research
Read More
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.
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [Marx08, FGMS12, DF13]), are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting $text{OPT}$ be the optimum and $N$ be the size of the input, is there an algorithm that runs in $t(text{OPT})text{poly}(N)$ time and outputs a solution of size $f(text{OPT})$, for any functions $t$ and $f$ that are independent of $N$ (for Clique, we want $f(text{OPT})=omega(1)$)? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i.e., there is no $o(text{OPT})$-FPT-approximation algorithm for Clique and no $f(text{OPT})$-FPT-approximation algorithm for DomSet, for any function $f$ (e.g., this holds even if $f$ is the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (Gap-ETH) [Dinur16, MR16], which states that no $2^{o(n)}$-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even $(1 - epsilon)$-satisfiable for some constant $epsilon > 0$. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, Maximum Subgraphs with Hereditary Properties, and Maximum Induced Matching in bipartite graphs. Additionally, we rule out $k^{o(1)}$-FPT-approximation algorithm for Densest $k$-Subgraph although this ratio does not yet match the trivial $O(k)$-approximation algorithm.
In $d$-Scattered Set we are given an (edge-weighted) graph and are asked to select at least $k$ vertices, so that the distance between any pair is at least $d$, thus generalizing Independent Set. We provide upper and lower bounds on the complexity of this problem with respect to various standard graph parameters. In particular, we show the following: - For any $dge2$, an $O^*(d^{textrm{tw}})$-time algorithm, where $textrm{tw}$ is the treewidth of the input graph. - A tight SETH-based lower bound matching this algorithms performance. These generalize known results for Independent Set. - $d$-Scattered Set is W[1]-hard parameterized by vertex cover (for edge-weighted graphs), or feedback vertex set (for unweighted graphs), even if $k$ is an additional parameter. - A single-exponential algorithm parameterized by vertex cover for unweighted graphs, complementing the above-mentioned hardness. - A $2^{O(textrm{td}^2)}$-time algorithm parameterized by tree-depth ($textrm{td}$), as well as a matching ETH-based lower bound, both for unweighted graphs. We complement these mostly negative results by providing an FPT approximation scheme parameterized by treewidth. In particular, we give an algorithm which, for any error parameter $epsilon > 0$, runs in time $O^*((textrm{tw}/epsilon)^{O(textrm{tw})})$ and returns a $d/(1+epsilon)$-scattered set of size $k$, if a $d$-scattered set of the same size exists.
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.
We study the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. We first show inapproximability of Min-Morse Matching within a factor of $2^{log^{(1-epsilon)}n}$. Our second result shows that Min-Morse Matching is ${bf W{[P]}}$-hard with respect to the standard parameter. Next, we show that Min-Morse Matching with standard parameterization has no FPT approximation algorithm for any approximation factor $rho$. The above hardness results are applicable to complexes of dimension $ge 2$. On the positive side, we provide a factor $O(frac{n}{log n})$ approximation algorithm for Min-Morse Matching on $2$-complexes, noting that no such algorithm is known for higher dimensional complexes. Finally, we devise discrete gradients with very few critical simplices for typical instances drawn from a fairly wide range of parameter values of the Costa-Farber model of random complexes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
