Parameterized Complexity of Coupon Coloring of Graphs
摘要
Given a graph G(V, E), a q-coupon coloring of G refers to a coloring \(f : V \rightarrow [q]\) such that the following is true for all \(v \in V\) : for all \(i \in [q]\) , there exists \(u \in N(v)\) such that \(f(u) = i\) . Given a graph G, the \(q\) -Coupon Coloring problem is to decide whether G admits a q-coupon coloring. The \(q\) -Coupon Coloring problem is shown to be NP-complete. We initiate the study of parameterized complexity of the \(q\) -Coupon Coloring problem. It is implied by existing results that parameterization by q is unlikely to admit FPT algorithms. We study the \(q\) -Coupon Coloring problem parameterized by structural parameters including neighborhood diversity, twin cover, distance to clique and treewidth of the graph. We show FPT algorithms when the parameter is neighborhood diversity, twin cover and distance to clique and prove tight lower bounds when the parameter is treewidth.