Fine-Grained Complexity of Rainbow Coloring and its Variants

Author Akanksha Agrawal



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.60.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Akanksha Agrawal

Cite AsGet BibTex

Akanksha Agrawal. Fine-Grained Complexity of Rainbow Coloring and its Variants. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.60

Abstract

Consider a graph G and an edge-coloring c_R:E(G) \rightarrow [k]. A rainbow path between u,v \in V(G) is a path P from u to v such that for all e,e' \in E(P), where e \neq e' we have c_R(e) \neq c_R(e'). In the Rainbow k-Coloring problem we are given a graph G, and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all u,v \in V(G) there is a rainbow path between u and v in G. Several variants of Rainbow k-Coloring have been studied, two of which are defined as follows. The Subset Rainbow k-Coloring takes as an input a graph G and a set S \subseteq V(G) \times V(G), and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all (u,v) \in S there is a rainbow path between u and v in G. The problem Steiner Rainbow k-Coloring takes as an input a graph G and a set S \subseteq V(G), and the objective is to decide if there exists c_R: E(G) \rightarrow [k] such that for all u,v \in S there is a rainbow path between u and v in G. In an attempt to resolve open problems posed by Kowalik et al. (ESA 2016), we obtain the following results. - For every k \geq 3, Rainbow k-Coloring does not admit an algorithm running in time 2^{o(|E(G)|)}n^{O(1)}, unless ETH fails. - For every k \geq 3, Steiner Rainbow k-Coloring does not admit an algorithm running in time 2^{o(|S|^2)}n^{O(1)}, unless ETH fails. - Subset Rainbow k-Coloring admits an algorithm running in time 2^{\OO(|S|)}n^{O(1)}. This also implies an algorithm running in time 2^{o(|S|^2)}n^{O(1)} for Steiner Rainbow k-Coloring, which matches the lower bound we obtain.
Keywords
  • Rainbow Coloring
  • Lower bound
  • ETH
  • Fine-grained Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split contraction: The untold story. In 34th Symposium on Theoretical Aspects of Computer Science, (STACS), pages 5:1-5:14, 2017. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  3. Prabhanjan Ananth, Meghana Nasre, and Kanthi K. Sarpatwar. Rainbow Connectivity: Hardness and Tractability. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 13, pages 241-251, 2011. Google Scholar
  4. Yair Caro, Arie Lev, Yehuda Roditty, Zsolt Tuza, and Raphael Yuster. On rainbow connection. Electronic Journal of Combinatorics, 15(1):R57, 2008. Google Scholar
  5. Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Raphael Yuster. Hardness and algorithms for rainbow connection. Journal of Combinatorial Optimization, 21(3):330-347, 2011. Google Scholar
  6. L. Sunil Chandran and Deepak Rajendraprasad. Rainbow colouring of split and threshold graphs. In 18th Annual International Conference: Computing and Combinatorics, (COCOON), pages 181-192, 2012. Google Scholar
  7. L. Sunil Chandran and Deepak Rajendraprasad. Inapproximability of rainbow colouring. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 153-162, 2013. Google Scholar
  8. Gary Chartrand, Garry L Johns, Kathleen A McKeon, and Ping Zhang. Rainbow connection in graphs. Mathematica Bohemica, 133(1):85-98, 2008. Google Scholar
  9. Gary Chartrand and Ping Zhang. Chromatic graph theory. CRC press, 2008. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. Tight bounds for graph homomorphism and subgraph isomorphism. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 1643-1649, 2016. Google Scholar
  11. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. Tight bounds for graph homomorphism and subgraph isomorphism. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1643-1649, 2016. Google Scholar
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  13. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  14. Keith Edwards. The harmonious chromatic number and the achromatic number. Surveys in Combinatorics, pages 13-48, 1997. Google Scholar
  15. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979. Google Scholar
  16. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  17. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  18. Christian Komusiewicz. Tight running time lower bounds for vertex deletion problems. arXiv preprint arXiv:1511.05449, 2015. Google Scholar
  19. Lukasz Kowalik and Juho Lauri. On finding rainbow and colorful paths. Theoretical Computer Science, 628(C):110-114, 2016. Google Scholar
  20. Lukasz Kowalik, Juho Lauri, and Arkadiusz Socala. On the fine-grained complexity of rainbow coloring. In 24th Annual European Symposium on Algorithms, (ESA), pages 58:1-58:16, 2016. Google Scholar
  21. V.B. Le and Z. Tuza. Finding Optimal Rainbow Connection is Hard. Preprints aus dem Institut für Informatik / CS. Inst. für Informatik, 2009. URL: https://books.google.no/books?id=0ErVPgAACAAJ.
  22. Sin-Min Lee and John Mitchem. An upper bound for the harmonious chromatic number. Journal of Graph Theory, 11(4):565-567, 1987. Google Scholar
  23. Xueliang Li, Yongtang Shi, and Yuefang Sun. Rainbow connections of graphs: A survey. Graphs and Combinatorics, 29(1):1-38, 2013. Google Scholar
  24. Xueliang Li and Yuefang Sun. Rainbow connections of graphs. Springer Science &Business Media, 2012. Google Scholar
  25. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, pages 41-71, 2011. Google Scholar
  26. Colin McDiarmid and Luo Xinhua. Upper bounds for harmonious coloring. Journal of Graph Theory, 15(6):629-636, 1991. Google Scholar
  27. M. Naor, L. J. Schulman, and A. Srinivasan. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pages 182-191, 1995. Google Scholar
  28. Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, and Xiao Zhou. On the rainbow connectivity of graphs: Complexity and fpt algorithms. Algorithmica, 67(2):161-179, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail