Document Open Access Logo

Toward a Dichotomy for Approximation of H-Coloring

Authors Akbar Rafiey , Arash Rafiey, Thiago Santos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.91.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Akbar Rafiey
  • Department of Computing Science, Simon Fraser University, Burnaby, Canada
Arash Rafiey
  • Indiana State University, Terre Haute, IN, USA
  • Simon Fraser University, Burnaby, Canada
Thiago Santos
  • Indiana State University, Terre Haute, IN, USA

Funding

  • Rafiey, Arash: Supported by NSF 1751765.

Acknowledgements

We are thankful to Andrei Bulatov for proofreading several drafts of the work and many valuable discussions that significantly improved the paper and its presentation.

Cite AsGet BibTex

Akbar Rafiey, Arash Rafiey, and Thiago Santos. Toward a Dichotomy for Approximation of H-Coloring. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 91:1-91:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.91

Abstract

Given two (di)graphs G, H and a cost function c:V(G) x V(H) -> Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)-> V(H) (a.k.a H-coloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph (i.e. symmetric digraph). For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with a conservative semi-lattice polymorphism or min-ordering), and k-arc digraphs (digraphs with an extended min-ordering). Specifically, we show that: - Dichotomy for Graphs: MinHOM(H) has a 2|V(H)|-approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a bi-arc graph), otherwise, it is inapproximable; - MinHOM(H) has a |V(H)|^2-approximation algorithm if H is a bi-arc digraph; - MinHOM(H) has a |V(H)|^2-approximation algorithm if H is a k-arc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of |V(H)|.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation algorithms
  • minimum cost homomorphism
  • randomized rounding

Metrics

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

Related Versions

References

  1. Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. J. Comput. Syst. Sci., 54(2):317-331, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1472.
  2. Per Austrin. Towards Sharp Inapproximability For Any 2-CSP. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 307-317, 2007. URL: http://dx.doi.org/10.1109/FOCS.2007.73.
  3. Guillaume Bagan, Arnaud Durand, Emmanuel Filiot, and Olivier Gauwin. Efficient Enumeration for Conjunctive Queries over X-underbar Structures. In Computer Science Logic, 24th International Workshop, CSL 2010, 19th Annual Conference of the EACSL, Brno, Czech Republic, August 23-27, 2010. Proceedings, pages 80-94, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15205-4_10.
  4. Amotz Bar-Noy, Mihir Bellare, Magnús M. Halldórsson, Hadas Shachnai, and Tami Tamir. On Chromatic Sums and Distributed Resource Allocation. Inf. Comput., 140(2):183-202, 1998. URL: http://dx.doi.org/10.1006/inco.1997.2677.
  5. Libor Barto. The Dichotomy for Conservative Constraint Satisfaction Problems Revisited. In Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011, June 21-24, 2011, Toronto, Ontario, Canada, pages 301-310, 2011. URL: http://dx.doi.org/10.1109/LICS.2011.25.
  6. Libor Barto, Andrei A. Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In Andrei A. Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/DFU.Vol7.15301.1.
  7. Richard C. Brewster, Tomás Feder, Pavol Hell, Jing Huang, and Gary MacGillivray. Near-Unanimity Functions and Varieties of Reflexive Graphs. SIAM J. Discrete Math., 22(3):938-960, 2008. URL: http://dx.doi.org/10.1137/S0895480103436748.
  8. Andrei A. Bulatov. Tractable conservative Constraint Satisfaction Problems. In 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 22-25 June 2003, Ottawa, Canada, Proceedings, page 321, 2003. URL: http://dx.doi.org/10.1109/LICS.2003.1210072.
  9. Andrei A. Bulatov. H-Coloring dichotomy revisited. Theor. Comput. Sci., 349(1):31-39, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.028.
  10. Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4):24:1-24:66, 2011. URL: http://dx.doi.org/10.1145/1970398.1970400.
  11. Andrei A. Bulatov. Conservative constraint satisfaction re-revisited. J. Comput. Syst. Sci., 82(2):347-356, 2016. URL: http://dx.doi.org/10.1016/j.jcss.2015.07.004.
  12. Andrei A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.37.
  13. David A. Cohen, Martin C. Cooper, Peter Jeavons, and Andrei A. Krokhin. The complexity of soft constraint satisfaction. Artif. Intell., 170(11):983-1016, 2006. URL: http://dx.doi.org/10.1016/j.artint.2006.04.002.
  14. David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei A. Krokhin, Robert Powell, and Stanislav Zivny. Binarisation for Valued Constraint Satisfaction Problems. SIAM J. Discrete Math., 31(4):2279-2300, 2017. URL: http://dx.doi.org/10.1137/16M1088107.
  15. Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity classifications of boolean constraint satisfaction problems, volume 7. SIAM, 2001. Google Scholar
  16. Víctor Dalmau, Andrei A. Krokhin, and Rajsekar Manokaran. Towards a characterization of constant-factor approximable finite-valued CSPs. J. Comput. Syst. Sci., 97:14-27, 2018. URL: http://dx.doi.org/10.1016/j.jcss.2018.03.003.
  17. Alina Ene, Jan Vondrák, and Yi Wu. Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 306-325, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.23.
  18. Tomás Feder, Pavol Hell, and Jing Huang. Bi-arc graphs and the complexity of list homomorphisms. Journal of Graph Theory, 42(1):61-80, 2003. URL: http://dx.doi.org/10.1002/jgt.10073.
  19. Tomás Feder, Pavol Hell, Peter Jonsson, Andrei A. Krokhin, and Gustav Nordh. Retractions to Pseudoforests. SIAM J. Discrete Math., 24(1):101-112, 2010. URL: http://dx.doi.org/10.1137/080738866.
  20. Tomás Feder and Moshe Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput., 28(1):57-104, 1998. URL: http://dx.doi.org/10.1137/S0097539794266766.
  21. Krzysztof Giaro, Robert Janczewski, Marek Kubale, and Michal Malafiejski. A 27/26-Approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs. In Approximation Algorithms for Combinatorial Optimization, 5th International Workshop, APPROX 2002, Rome, Italy, September 17-21, 2002, Proceedings, pages 135-145, 2002. URL: http://dx.doi.org/10.1007/3-540-45753-4_13.
  22. Michel X. Goemans and David P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6):1115-1145, 1995. URL: http://dx.doi.org/10.1145/227683.227684.
  23. Gregory Z. Gutin, Pavol Hell, Arash Rafiey, and Anders Yeo. A dichotomy for minimum cost graph homomorphisms. Eur. J. Comb., 29(4):900-911, 2008. URL: http://dx.doi.org/10.1016/j.ejc.2007.11.012.
  24. Gregory Z. Gutin, Arash Rafiey, and Anders Yeo. Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs. SIAM J. Discrete Math., 22(4):1624-1639, 2008. URL: http://dx.doi.org/10.1137/060668316.
  25. Gregory Z. Gutin, Arash Rafiey, Anders Yeo, and Michael Tso. Level of repair analysis and minimum cost homomorphisms of graphs. Discrete Applied Mathematics, 154(6):881-889, 2006. URL: http://dx.doi.org/10.1016/j.dam.2005.06.012.
  26. Wolfgang Gutjahr, Emo Welzl, and Gerhard J. Woeginger. Polynomial graph-colorings. Discrete Applied Mathematics, 35(1):29-45, 1992. URL: http://dx.doi.org/10.1016/0166-218X(92)90294-K.
  27. Magnús M. Halldórsson, Guy Kortsarz, and Hadas Shachnai. Minimizing Average Completion of Dedicated Tasks and Interval Graphs. In Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18-20, 2001, Proceedings, pages 114-126, 2001. URL: http://dx.doi.org/10.1007/3-540-44666-4_15.
  28. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. URL: http://dx.doi.org/10.1145/502090.502098.
  29. Pavol Hell, Jing Huang, Ross M. McConnell, and Arash Rafiey. Interval-Like Graphs and Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, pages 68:1-68:13, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2018.68.
  30. Pavol Hell, Monaldo Mastrolilli, Mayssam Mohammadi Nevisi, and Arash Rafiey. Approximation of Minimum Cost Homomorphisms. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pages 587-598, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_51.
  31. Pavol Hell and Jaroslav Nesetril. On the complexity of H-coloring. J. Comb. Theory, Ser. B, 48(1):92-110, 1990. URL: http://dx.doi.org/10.1016/0095-8956(90)90132-J.
  32. Pavol Hell and Jaroslav Nesetril. Graphs and homomorphisms. Oxford University Press, 2004. Google Scholar
  33. Pavol Hell and Arash Rafiey. The Dichotomy of List Homomorphisms for Digraphs. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1703-1713, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.131.
  34. Pavol Hell and Arash Rafiey. Monotone Proper Interval Digraphs and Min-Max Orderings. SIAM J. Discrete Math., 26(4):1576-1596, 2012. URL: http://dx.doi.org/10.1137/100783844.
  35. Pavol Hell and Arash Rafiey. The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs. SIAM J. Discrete Math., 26(4):1597-1608, 2012. URL: http://dx.doi.org/10.1137/100783856.
  36. Pavol Hell and Arash Rafiey. Bi-Arc Digraphs and Conservative Polymorphisms. CoRR, abs/1608.03368, 2016. URL: http://arxiv.org/abs/1608.03368.
  37. Klaus Jansen. Approximation Results for the Optimum Cost Chromatic Partition Problem. J. Algorithms, 34(1):54-89, 2000. URL: http://dx.doi.org/10.1006/jagm.1999.1022.
  38. Tao Jiang and Douglas B West. Coloring of trees with minimum sum of colors. Journal of Graph Theory, 32(4):354-358, 1999. Google Scholar
  39. Peter Jonsson and Gustav Nordh. Introduction to the Maximum SolutionProblem. In Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar]., pages 255-282, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92800-3_10.
  40. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson. The Approximability of Constraint Satisfaction Problems. SIAM J. Comput., 30(6):1863-1920, 2000. URL: http://dx.doi.org/10.1137/S0097539799349948.
  41. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 146-154, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.49.
  42. Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolinek. The Complexity of General-Valued CSPs. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1246-1258, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.80.
  43. Leo G. Kroon, Arunabha Sen, Haiyong Deng, and Asim Roy. The Optimal Cost Chromatic Partition Problem for Trees and Interval Graphs. In Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG '96, Cadenabbia (Como), Italy, June 12-14, 1996, Proceedings, pages 279-292, 1996. URL: http://dx.doi.org/10.1007/3-540-62559-3_23.
  44. Ewa Kubicka and Allen J. Schwenk. An Introduction to Chromatic Sums. In Computer Trends in the 1990s - Proceedings of the 1989 ACM 17th Annual Computer Science Conference, Louisville, Kentucky, USA, February 21-23, 1989, pages 39-45, 1989. URL: http://dx.doi.org/10.1145/75427.75430.
  45. Michael Lewin, Dror Livnat, and Uri Zwick. Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems. In Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA, USA, May 27-29, 2002, Proceedings, pages 67-82, 2002. URL: http://dx.doi.org/10.1007/3-540-47867-1_6.
  46. Gary MacGillivray and Jacobus Swarts. The C_k-extended graft construction. Discrete Applied Mathematics, 159(12):1293-1301, 2011. URL: http://dx.doi.org/10.1016/j.dam.2011.04.006.
  47. Konstantin Makarychev and Yury Makarychev. Approximation Algorithms for CSPs. In Andrei A. Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 287-325. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/DFU.Vol7.15301.11.
  48. Monaldo Mastrolilli and Arash Rafiey. On the approximation of minimum cost homomorphism to bipartite graphs. Discrete Applied Mathematics, 161(4-5):670-676, 2013. URL: http://dx.doi.org/10.1016/j.dam.2011.05.002.
  49. Akbar Rafiey, Arash Rafiey, and Thiago Santos. Toward a Dichotomy for Approximation of H-coloring. CoRR, abs/1902.02201, 2019. URL: http://arxiv.org/abs/1902.02201.
  50. Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 245-254, 2008. URL: http://dx.doi.org/10.1145/1374376.1374414.
  51. Rustem Takhanov. A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem. In 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, pages 657-668, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2493.
  52. Johan Thapper and Stanislav Zivny. The complexity of finite-valued CSPs. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 695-704, 2013. URL: http://dx.doi.org/10.1145/2488608.2488697.
  53. Hannes Uppman. The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 804-815, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_68.
  54. Hannes Uppman. Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, pages 651-662, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2014.651.
  55. Dmitriy Zhuk. A Proof of CSP Dichotomy Conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331-342, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.38.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact