Abstract
The CSP dichotomy conjecture has been recently established, but a number of other dichotomy questions remain open, including the dichotomy classification of list homomorphism problems for signed graphs. Signed graphs arise naturally in many contexts, including for instance nowhere-zero flows for graphs embedded in non-orientable surfaces. For a fixed signed graph \(\widehat{H}\), the list homomorphism problem asks whether an input signed graph \(\widehat{G}\) with lists \(L(v) \subseteq V(\widehat{H}), v \in V(\widehat{G}),\) admits a homomorphism f to \(\widehat{H}\) with all \(f(v) \in L(v), v \in V(\widehat{G})\).
Usually, a dichotomy classification is easier to obtain for list homomorphisms than for homomorphisms, but in the context of signed graphs a structural classification of the complexity of list homomorphism problems has not even been conjectured, even though the classification of the complexity of homomorphism problems is known.
Kim and Siggers have conjectured a structural classification in the special case of “weakly balanced" signed graphs. We confirm their conjecture for reflexive and irreflexive signed graphs; this generalizes previous results on weakly balanced signed trees, and weakly balanced separable signed graphs [1,2,3]. In the reflexive case, the result was first presented in [19], where the proof relies on a result in this paper. The irreflexive result is new, and its proof depends on first deriving a theorem on extensions of min orderings of (unsigned) bipartite graphs, which is interesting on its own.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The details of this can be found in our arXiv paper [4].
References
Bok, J., Brewster, R., Feder, T., Hell, P., Jedličková, N.: List homomorphisms to separable signed graphs. In: Balachandran, N., Inkulu, R. (eds.) CALDAM 2022. LNCS, vol. 13179, pp. 22–35. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-95018-7_3
Bok, J., Brewster, R.C., Feder, T., Hell, P., Jedličková, N.: List homomorphism problems for signed graphs. In: Esparza, J., Kráľ, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 170, pp. 20:1–20:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl (2020). https://drops.dagstuhl.de/opus/volltexte/2020/12688
Bok, J., Brewster, R.C., Feder, T., Hell, P., Jedličková, N.: List homomorphism problems for signed graphs (2021, submitted). https://arxiv.org/abs/2005.05547
Bok, J., Brewster, R.C., Hell, P., Jedličková, N., Rafiey, A.: Min orderings and list homomorphism dichotomies for signed and unsigned graphs. CoRR abs/2206.01068 (2022). https://arxiv.org/abs/2206.01068
Bok, J., Brewster, R.C., Hell, P., Jedličková, N.: List homomorphisms of signed graphs. In: Bordeaux Graph Workshop, pp. 81–84 (2019)
Brewster, R.C., Foucaud, F., Hell, P., Naserasr, R.: The complexity of signed graph and edge-coloured graph homomorphisms. Discret. Math. 340(2), 223–235 (2017)
Brewster, R.C., Siggers, M.: A complexity dichotomy for signed \(H\)-colouring. Discret. Math. 341(10), 2768–2773 (2018)
Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 319–330. IEEE (2017)
Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica 19(4), 487–505 (1999)
Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms. J. Graph Theory 42(1), 61–80 (2003)
Feder, T., Hell, P., Huang, J., Rafiey, A.: Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. Discret. Appl. Math. 160(6), 697–707 (2012)
Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. In: STOC, pp. 612–622 (1993)
Guenin, B.: A characterization of weakly bipartite graphs. J. Combin. Theory Ser. B 83(1), 112–168 (2001)
Guenin, B.: Packing odd circuit covers: a conjecture (2005). Manuscript
Hell, P., Mastrolilli, M., Nevisi, M.M., Rafiey, A.: Approximation of minimum cost homomorphisms. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 587–598. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33090-2_51
Hell, P., Nešetřil, J.: On the complexity of \(H\)-coloring. J. Combin. Theory Ser. B 48(1), 92–110 (1990)
Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications, vol. 28. Oxford University Press, Oxford (2004)
Kaiser, T., Lukoťka, R., Rollová, E.: Nowhere-zero flows in signed graphs: a survey. In: Selected Topics in Graph Theory and Its Applications. Lecture Notes of Seminario Interdisciplinare di Matematica, vol. 14, pp. 85–104. Seminario Interdisciplinare di Matematica (S.I.M.), Potenza (2017)
Kim, H., Siggers, M.: Towards a dichotomy for the switch list homomorphism problem for signed graphs (2021). https://arxiv.org/abs/2104.07764
Naserasr, R., Sopena, E., Zaslavsky, T.: Homomorphisms of signed graphs: an update. European J. Combin. 91, Paper No. 103222, 20 (2021). https://doi.org/10.1016/j.ejc.2020.103222
Schrijver, A.: A short proof of Guenin’s characterization of weakly bipartite graphs. J. Combin. Theory Ser. B 85(2), 255–260 (2002)
Zaslavsky, T.: Signed graph coloring. Discrete Math. 39(2), 215–228 (1982)
Zaslavsky, T.: A mathematical bibliography of signed and gain graphs and allied areas. Electron. J. Combin. 5, Dynamic Surveys 8, 124 (1998). Manuscript prepared with Marge Pratt
Zhuk, D.: A proof of CSP dichotomy conjecture. In: 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, pp. 331–342. IEEE Computer Society, Los Alamitos (2017)
Acknowledgements
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 810115 - DYNASNET). J. Bok and N. Jedličková were also partially supported by GAUK 370122 and SVV-2020-260578. R. Brewster gratefully acknowledges support from the NSERC Canada Discovery Grant programme. P. Hell gratefully acknowledges support from the NSERC Canada Discovery Grant programme. A. Rafiey gratefully acknowledges support from the grant NSF1751765.
We thank Reza Naserasr and Mark Siggers for helpful discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Bok, J., Brewster, R.C., Hell, P., Jedličková, N., Rafiey, A. (2022). Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs. In: Castañeda, A., Rodríguez-Henríquez, F. (eds) LATIN 2022: Theoretical Informatics. LATIN 2022. Lecture Notes in Computer Science, vol 13568. Springer, Cham. https://doi.org/10.1007/978-3-031-20624-5_31
Download citation
DOI: https://doi.org/10.1007/978-3-031-20624-5_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20623-8
Online ISBN: 978-3-031-20624-5
eBook Packages: Computer ScienceComputer Science (R0)