research-article
Authors: Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková
Volume 1001, Issue C
Published: 17 July 2024 Publication History
- 0citation
- 0
- Downloads
Metrics
Total Citations0Total Downloads0Last 12 Months0
Last 6 weeks0
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
- View Options
- References
- Media
- Tables
- Share
Abstract
The complexity of the list hom*omorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees [4] and reflexive signed graphs [25]. Irreflexive signed graphs are in a certain sense the heart of the problem, as noted by a recent paper of Kim and Siggers. We focus on a special class of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, which we call separable signed graphs. We classify the complexity of list hom*omorphisms to these separable signed graphs; we believe that these signed graphs will play an important role for the general resolution of the irreflexive case. We also relate our results to a conjecture of Kim and Siggers concerning the special case of semi-balanced irreflexive signed graphs; we have proved the conjecture in another paper, and the present results add structural information to that topic.
References
[1]
Jan Bok, Richard C. Brewster, Tomás Feder, Pavol Hell, Nikola Jedličková, List hom*omorphisms to separable signed graphs, in: Niranjan Balachandran, R. Inkulu (Eds.), Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, Puduch*erry, India, February 10–12, 2022, Proceedings, in: Lecture Notes in Computer Science, vol. 13179, Springer, 2022, pp. 22–35. https://doi.org/10.1007/978-3-030-95018-7_3.
[2]
Bok, Jan; Brewster, Richard C.; Feder, Tomás; Hell, Pavol; Jedličková, Nikola (2021): List hom*omorphism problems for signed graphs. arXiv:2005.05547.
[3]
Jan Bok, Richard C. Brewster, Tomás Feder, Pavol Hell, Nikola Jedličková, List hom*omorphism problems for signed trees, Discrete Math. 346 (3) (2023) 24 https://doi.org/10.1016/j.disc.2022.113257.
[4]
Jan Bok, Richard C. Brewster, Tomás Feder, Pavol Hell, Nikola Jedličková, List hom*omorphism problems for signed graphs, in: Javier Esparza, Daniel Kráľ (Eds.), 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), in: Leibniz International Proceedings in Informatics (LIPIcs), vol. 170, Dagstuhl, Germany, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 20:1–20:14,. https://drops.dagstuhl.de/opus/volltexte/2020/12688.
[5]
Jan Bok, Richard C. Brewster, Pavol Hell, Nikola Jedličková, List hom*omorphisms of signed graphs, in: Bordeaux Graph Workshop, 2019, pp. 81–84.
[6]
Jan Bok, Richard C. Brewster, Pavol Hell, Nikola Jedličková, Arash Rafiey, Min orderings and list hom*omorphism dichotomies for signed and unsigned graphs, in: Armando Castañeda, Francisco Rodríguez-Henríquez (Eds.), LATIN 2022: Theoretical Informatics - 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings, in: Lecture Notes in Computer Science, vol. 13568, Springer, 2022, pp. 510–526. https://doi.org/10.1007/978-3-031-20624-5_31.
[7]
Bok, Jan; Brewster, Richard C.; Hell, Pavol; Jedličková, Nikola; Rafiey, Arash (2023): Min orderings and list hom*omorphism dichotomies for signed and unsigned graphs. arXiv:2206.01068.
[8]
Richard C. Brewster, Florent Foucaud, Pavol Hell, Reza Naserasr, The complexity of signed graph and edge-coloured graph hom*omorphisms, Discrete Math. 340 (2) (2017) 223–235.
[9]
Richard C. Brewster, Timothy Graves, Edge-switching hom*omorphisms of edge-coloured graphs, Discrete Math. 309 (18) (2009) 5540–5546.
[10]
Richard C. Brewster, Mark Siggers, A complexity dichotomy for signed h-colouring, Discrete Math. 341 (10) (2018) 2768–2773.
[11]
Andrei A. Bulatov, Complexity of conservative constraint satisfaction problems, ACM Trans. Comput. Log. 12 (4) (2011) 1–66.
[12]
Andrei A. Bulatov, A dichotomy theorem for nonuniform CSPs, in: 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp. 319–330.
[13]
N. Creignou, S. Khanna, M. Sudan, Complexity classifications of Boolean constraint satisfaction problems, in: SIAM Monographs on Discrete Mathematics and Applications, 2001.
[14]
Tomás Feder, Pavol Hell, List hom*omorphisms to reflexive graphs, J. Comb. Theory, Ser. B 72 (2) (1998) 236–250.
[15]
Tomás Feder, Pavol Hell, Jing Huang, List hom*omorphisms and circular arc graphs, Combinatorica 19 (4) (1999) 487–505.
[16]
Tomás Feder, Pavol Hell, Jing Huang, Bi-arc graphs and the complexity of list hom*omorphisms, J. Graph Theory 42 (1) (2003) 61–80.
[17]
Tomás Feder, Moshe Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, in: STOC, 1993, pp. 612–622.
[18]
Bertrand Guenin, Packing odd circuit covers: a conjecture, 2005, Manuscript.
[19]
Frank Harary, On the notion of balance of a signed graph, Mich. Math. J. 2 (1955) 143–146. 1953/54.
[20]
Frank Harary, Jerald A. Kabell, A simple algorithm to detect balance in signed graphs, Math. Soc. Sci. 1 (1) (1980/81) 131–136.
[21]
Pavol Hell, Monaldo Mastrolilli, Mayssam Mohammadi Nevisi, Arash Rafiey, Approximation of minimum cost hom*omorphisms, in: Algorithms—ESA 2012, in: Lecture Notes in Comput. Sci., vol. 7501, Springer, Heidelberg, 2012, pp. 587–598. https://doi.org/10.1007/978-3-642-33090-2_51.
[22]
Pavol Hell, Jaroslav Nešetřil, On the complexity of H-coloring, J. Comb. Theory, Ser. B 48 (1) (1990) 92–110.
Digital Library
[23]
Pavol Hell, Jaroslav Nešetřil, Graphs and hom*omorphisms, Oxford Lecture Series in Mathematics and Its Applications, vol. 28, Oxford University Press, Oxford, 2004.
[24]
Peter Jeavons, On the algebraic structure of combinatorial problems, Theor. Comput. Sci. 200 (1–2) (1998) 185–204.
[25]
Kim, Hyobin; Siggers, Mark (2021): Towards a dichotomy for the switch list hom*omorphism problem for signed graphs. arXiv:2104.07764.
[26]
Reza Naserasr, Edita Rollová, Éric Sopena, hom*omorphisms of signed graphs, J. Graph Theory 79 (3) (2015) 178–212.
[27]
Reza Naserasr, Éric Sopena, Thomas Zaslavsky, hom*omorphisms of signed graphs: an update, Eur. J. Comb. 91 (2021) 20 https://doi.org/10.1016/j.ejc.2020.103222.
[28]
Thomas J. Schaefer, The complexity of satisfiability problems, in: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, 1978, pp. 216–226.
[29]
Thomas Zaslavsky, Characterizations of signed graphs, J. Graph Theory 5 (4) (1981) 401–406.
[30]
Thomas Zaslavsky, Signed graph coloring, Discrete Math. 39 (2) (1982) 215–228.
[31]
Thomas Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1) (1982) 47–74.
[32]
Thomas Zaslavsky, Is there a matroid theory of signed graph embedding?, Ars Comb. 45 (1997) 129–141.
[33]
Thomas Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Comb. 5 (Dynamic Surveys 8) (1998) 124. Manuscript prepared with Marge Pratt.
[34]
Dmitriy Zhuk, A proof of CSP dichotomy conjecture, in: 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp. 331–342.
Recommendations
- List hom*omorphism problems for signed trees
Abstract
We consider hom*omorphisms of signed graphs from a computational perspective. In particular, we study the list hom*omorphism problem seeking a hom*omorphism of an input signed graph ( G , σ ), equipped with lists L ( v ) ⊆ V ( H ) , v ∈ V ...
Read More
- hom*omorphisms of Signed Graphs
A signed graph [G,Σ] is a graph G together with an assignment of signs + and - to all the edges of G where Σ is the set of negative edges. Furthermore [G,Σ1] and [G,Σ2] are considered to be equivalent if the symmetric difference of Σ1 and Σ2 is an edge ...
Read More
- Degree choosable signed graphs
A signed graph is a graph in which each edge is labeled with +1 or 1. A (proper) vertex coloring of a signed graph is a mapping that assigns to each vertex vV(G) a color (v)Z such that every edge vw of G satisfies (v)(vw)(w), where (vw) is the sign of ...
Read More
Comments
Information & Contributors
Information
Published In
Theoretical Computer Science Volume 1001, Issue C
Jun 2024
111 pages
ISSN:0304-3975
Issue’s Table of Contents
Elsevier B.V.
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 17 July 2024
Author Tags
- Signed graphs
- Graph hom*omorphism
- Complexity
- Dichotomy
- List hom*omorphism
Qualifiers
- Research-article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
Total Citations
Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Other Metrics
View Author Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
Media
Figures
Other
Tables
