Graph homomorphism reconfiguration and frozen H-colorings. Brewster, R. C., Lee, J., Moore, B., Noel, J. A., & Siggers, M. Journal of Graph Theory, December, 2019.
Paper doi abstract bibtex For a fixed graph H, the reconfiguration problem for H-colorings (ie, homomorphisms to H) asks: given a graph G and two H-colorings φ and ψ of G, does there exist a sequence f0,…,fm of H-colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i\textlessm and uv∈E(G)? If the graph G is loop-free, then this is the equivalent to asking whether it possible to transform φ into ψ by changing the color of one vertex at a time such that all intermediate mappings are H-colorings. In the affirmative, we say that φ reconfigures to ψ. Currently, the complexity of deciding whether an H-coloring φ reconfigures to an H-coloring ψ is only known when H is a clique, a circular clique, a C4-free graph, or in a few other cases which are easily derived from these. We show that this problem is PSPACE-complete when H is an odd wheel. An important notion in the study of reconfiguration problems for H-colorings is that of a frozen H-coloring; that is, an H-coloring φ such that φ does not reconfigure to any H-coloring ψ such that ψ≠φ. We obtain an explicit dichotomy theorem for the problem of deciding whether a given graph G admits a frozen H-coloring. The hardness proof involves a reduction from a constraint satisfaction problem which is shown to be nondeterministic polynomial time NP-complete by establishing the nonexistence of a certain type of polymorphism.
@article{brewster_graph_2019,
title = {Graph homomorphism reconfiguration and frozen {H}-colorings},
volume = {n/a},
copyright = {© 2019 Wiley Periodicals, Inc.},
issn = {1097-0118},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22530},
doi = {10.1002/jgt.22530},
abstract = {For a fixed graph H, the reconfiguration problem for H-colorings (ie, homomorphisms to H) asks: given a graph G and two H-colorings φ and ψ of G, does there exist a sequence f0,…,fm of H-colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i{\textless}m and uv∈E(G)? If the graph G is loop-free, then this is the equivalent to asking whether it possible to transform φ into ψ by changing the color of one vertex at a time such that all intermediate mappings are H-colorings. In the affirmative, we say that φ reconfigures to ψ. Currently, the complexity of deciding whether an H-coloring φ reconfigures to an H-coloring ψ is only known when H is a clique, a circular clique, a C4-free graph, or in a few other cases which are easily derived from these. We show that this problem is PSPACE-complete when H is an odd wheel. An important notion in the study of reconfiguration problems for H-colorings is that of a frozen H-coloring; that is, an H-coloring φ such that φ does not reconfigure to any H-coloring ψ such that ψ≠φ. We obtain an explicit dichotomy theorem for the problem of deciding whether a given graph G admits a frozen H-coloring. The hardness proof involves a reduction from a constraint satisfaction problem which is shown to be nondeterministic polynomial time NP-complete by establishing the nonexistence of a certain type of polymorphism.},
language = {en},
number = {n/a},
urldate = {2020-01-22},
journal = {Journal of Graph Theory},
author = {Brewster, Richard C. and Lee, Jae-Baek and Moore, Benjamin and Noel, Jonathan A. and Siggers, Mark},
month = dec,
year = {2019},
keywords = {complexity, graph homomorphism, recoloring, reconfiguration}
}
Downloads: 0
{"_id":"xNaweggKXyzePsFao","bibbaseid":"brewster-lee-moore-noel-siggers-graphhomomorphismreconfigurationandfrozenhcolorings-2019","authorIDs":[],"author_short":["Brewster, R. C.","Lee, J.","Moore, B.","Noel, J. A.","Siggers, M."],"bibdata":{"bibtype":"article","type":"article","title":"Graph homomorphism reconfiguration and frozen H-colorings","volume":"n/a","copyright":"© 2019 Wiley Periodicals, Inc.","issn":"1097-0118","url":"https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22530","doi":"10.1002/jgt.22530","abstract":"For a fixed graph H, the reconfiguration problem for H-colorings (ie, homomorphisms to H) asks: given a graph G and two H-colorings φ and ψ of G, does there exist a sequence f0,…,fm of H-colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i\\textlessm and uv∈E(G)? If the graph G is loop-free, then this is the equivalent to asking whether it possible to transform φ into ψ by changing the color of one vertex at a time such that all intermediate mappings are H-colorings. In the affirmative, we say that φ reconfigures to ψ. Currently, the complexity of deciding whether an H-coloring φ reconfigures to an H-coloring ψ is only known when H is a clique, a circular clique, a C4-free graph, or in a few other cases which are easily derived from these. We show that this problem is PSPACE-complete when H is an odd wheel. An important notion in the study of reconfiguration problems for H-colorings is that of a frozen H-coloring; that is, an H-coloring φ such that φ does not reconfigure to any H-coloring ψ such that ψ≠φ. We obtain an explicit dichotomy theorem for the problem of deciding whether a given graph G admits a frozen H-coloring. The hardness proof involves a reduction from a constraint satisfaction problem which is shown to be nondeterministic polynomial time NP-complete by establishing the nonexistence of a certain type of polymorphism.","language":"en","number":"n/a","urldate":"2020-01-22","journal":"Journal of Graph Theory","author":[{"propositions":[],"lastnames":["Brewster"],"firstnames":["Richard","C."],"suffixes":[]},{"propositions":[],"lastnames":["Lee"],"firstnames":["Jae-Baek"],"suffixes":[]},{"propositions":[],"lastnames":["Moore"],"firstnames":["Benjamin"],"suffixes":[]},{"propositions":[],"lastnames":["Noel"],"firstnames":["Jonathan","A."],"suffixes":[]},{"propositions":[],"lastnames":["Siggers"],"firstnames":["Mark"],"suffixes":[]}],"month":"December","year":"2019","keywords":"complexity, graph homomorphism, recoloring, reconfiguration","bibtex":"@article{brewster_graph_2019,\n\ttitle = {Graph homomorphism reconfiguration and frozen {H}-colorings},\n\tvolume = {n/a},\n\tcopyright = {© 2019 Wiley Periodicals, Inc.},\n\tissn = {1097-0118},\n\turl = {https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22530},\n\tdoi = {10.1002/jgt.22530},\n\tabstract = {For a fixed graph H, the reconfiguration problem for H-colorings (ie, homomorphisms to H) asks: given a graph G and two H-colorings φ and ψ of G, does there exist a sequence f0,…,fm of H-colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i{\\textless}m and uv∈E(G)? If the graph G is loop-free, then this is the equivalent to asking whether it possible to transform φ into ψ by changing the color of one vertex at a time such that all intermediate mappings are H-colorings. In the affirmative, we say that φ reconfigures to ψ. Currently, the complexity of deciding whether an H-coloring φ reconfigures to an H-coloring ψ is only known when H is a clique, a circular clique, a C4-free graph, or in a few other cases which are easily derived from these. We show that this problem is PSPACE-complete when H is an odd wheel. An important notion in the study of reconfiguration problems for H-colorings is that of a frozen H-coloring; that is, an H-coloring φ such that φ does not reconfigure to any H-coloring ψ such that ψ≠φ. We obtain an explicit dichotomy theorem for the problem of deciding whether a given graph G admits a frozen H-coloring. The hardness proof involves a reduction from a constraint satisfaction problem which is shown to be nondeterministic polynomial time NP-complete by establishing the nonexistence of a certain type of polymorphism.},\n\tlanguage = {en},\n\tnumber = {n/a},\n\turldate = {2020-01-22},\n\tjournal = {Journal of Graph Theory},\n\tauthor = {Brewster, Richard C. and Lee, Jae-Baek and Moore, Benjamin and Noel, Jonathan A. and Siggers, Mark},\n\tmonth = dec,\n\tyear = {2019},\n\tkeywords = {complexity, graph homomorphism, recoloring, reconfiguration}\n}\n\n","author_short":["Brewster, R. C.","Lee, J.","Moore, B.","Noel, J. A.","Siggers, M."],"key":"brewster_graph_2019","id":"brewster_graph_2019","bibbaseid":"brewster-lee-moore-noel-siggers-graphhomomorphismreconfigurationandfrozenhcolorings-2019","role":"author","urls":{"Paper":"https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22530"},"keyword":["complexity","graph homomorphism","recoloring","reconfiguration"],"downloads":0},"bibtype":"article","biburl":"https://api.zotero.org/users/1532883/collections/P6RMVNVQ/items?key=L1ryLzoM1eiuIIjZzxPZ0JEV&format=bibtex&limit=100","creationDate":"2020-02-21T11:15:12.105Z","downloads":0,"keywords":["complexity","graph homomorphism","recoloring","reconfiguration"],"search_terms":["graph","homomorphism","reconfiguration","frozen","colorings","brewster","lee","moore","noel","siggers"],"title":"Graph homomorphism reconfiguration and frozen H-colorings","year":2019,"dataSources":["QbDyeABmJNi4jvafK"]}