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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Parameterized Complexity of Coupon Coloring of Graphs

  • Pradeesha Ashok,
  • Pradyun Devarakonda,
  • Shiven Phogat,
  • Swaroop A. Ram Rayala,
  • J. A. Sherin

摘要

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.