Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFrom Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
225
0
0.0
(
0
)
Added by
Pasin Manurangsi
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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
We study a family of generalizations of Edge Dominating Set on directed graphs called Directed $(p,q)$-Edge Dominating Set. In this problem an arc $(u,v)$ is said to dominate itself, as well as all arcs which are at distance at most $q$ from $v$, or at distance at most $p$ to $u$. First, we give significantly improved FPT algorithms for the two most important cases of the problem, $(0,1)$-dEDS and $(1,1)$-dEDS (that correspond
We show that the k-Dominating Set problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j} as a subgraph, for any fixed i, j >= 1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded- degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner.
A rainbow $q$-coloring of a $k$-uniform hypergraph is a $q$-coloring of the vertex set such that every hyperedge contains all $q$ colors. We prove that given a rainbow $(k - 2lfloor sqrt{k}rfloor)$-colorable $k$-uniform hypergraph, it is NP-hard to find a normal $2$-coloring. Previously, this was only known for rainbow $lfloor k/2 rfloor$-colorable hypergraphs (Guruswami and Lee, SODA 2015). We also study a generalization which we call rainbow $(q, p)$-coloring, defined as a coloring using $q$ colors such that every hyperedge contains at least $p$ colors. We prove that given a rainbow $(k - lfloor sqrt{kc} rfloor, k- lfloor3sqrt{kc} rfloor)$-colorable $k$ uniform hypergraph, it is NP-hard to find a normal $c$-coloring for any $c = o(k)$. The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J. Comb. Theory. 1990) using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.
This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. We consider important graph classes, distinguishing between connected and not necessarily connected graphs. For the classic graph classes of trees, bipartite, planar, and general graphs, we obtain tight results in almost all cases. We also derive upper and lower bounds for the class of bounded-degree graphs. From these analyses, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithms disadvantage.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
