Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Inapproximability of Rainbow Coloring
192
0
0.0
(
0
)
Added by
Aditya Potukuchi
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal $t$-agreeing families of $[q]^n$. Specifically, using theorems of Frankl-Tokushige [FT99], Ahlswede-Khachatrian [AK98] and Frankl [F76] on the size of such families, we give simple and unified proofs of quasi NP-hardness of the following problems: $bullet$ coloring a $3$ colorable $4$-uniform hypergraph with $(log n)^delta$ many colors $bullet$ coloring a $3$ colorable $3$-uniform hypergraph with $tilde{O}(sqrt{log log n})$ many colors $bullet$ coloring a $2$ colorable $6$-uniform hypergraph with $(log n)^delta$ many colors $bullet$ coloring a $2$ colorable $4$-uniform hypergraph with $tilde{O}(sqrt{log log n})$ many colors where $n$ is the number of vertices of the hypergraph and $delta>0$ is a universal constant.
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order $sigma$, the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering $sigma$, i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, Grundy Coloring has been examined for its structural and algorithmic aspects. A brute-force $f(k)n^{2^{k-1}}$-time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where $k$ is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on $k$ in the exponent of $n$ can be avoided or reduced, and its answer seemed elusive until now. We prove that Grundy Coloring is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-Chromatic Core is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS 17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on $K_{t,t}$-free graphs for b-Chromatic Core and Partial Grundy Coloring, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.
We study the problem of computing the $prightarrow q$ norm of a matrix $A in R^{m times n}$, defined as [ |A|_{prightarrow q} ~:=~ max_{x ,in, R^n setminus {0}} frac{|Ax|_q}{|x|_p} ] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=infty$, $q=1$), and has been widely studied in various regimes. When $p geq q$, the problem exhibits a dichotomy: constant factor approximation algorithms are known if $2 in [q,p]$, and the problem is hard to approximate within almost polynomial factors when $2 otin [q,p]$. The regime when $p < q$, known as emph{hypercontractive norms}, is particularly significant for various applications but much less well understood. The case with $p = 2$ and $q > 2$ was studied by [Barak et al, STOC12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation is known for these problems for any $p < q$. We study the hardness of approximating matrix norms in both the above cases and prove the following results: - We show that for any $1< p < q < infty$ with $2 otin [p,q]$, $|A|_{prightarrow q}$ is hard to approximate within $2^{O(log^{1-epsilon}!n)}$ assuming $NP otsubseteq BPTIME(2^{log^{O(1)}!n})$. This suggests that, similar to the case of $p geq q$, the hypercontractive setting may be qualitatively different when $2$ does not lie between $p$ and $q$. - For all $p geq q$ with $2 in [q,p]$, we show $|A|_{prightarrow q}$ is hard to approximate within any factor than $1/(gamma_{p^*} cdot gamma_q)$, where for any $r$, $gamma_r$ denotes the $r^{th}$ norm of a gaussian, and $p^*$ is the dual norm of $p$.
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $operatorname{rb-index}(k)$ be the maximum of $operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $operatorname{rb-index}(k) eq k$, and we prove that for $kge 5$, [ frac{40lfloor (k-1)/2 rfloor -8}{19} %Birgit: leqoperatorname{rb-index}(k)leq 10 bigglfloorfrac{k}{7}biggrfloor + 11. ] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 lfloorfrac{k}{7}rfloor + 11$ vertices can be computed in $O(nlog n)$ time.
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
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
