Towards A Dichotomy for the List Switch Homomorphism Problem for Signed Graph
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We make advances towards a structural characterisation of the signed graphs H for which the list switch H-colouring problem List-S-Hom(H) can be solved in polynomial time. We conjecture two different characterisations, the second refining the first, in the case that the graph H can be switched to a graph in which every negative edge is also positive. Using a recent proof of the first characterisations for reflexive signed graphs, by Bok et. al., we prove the second characterisation for reflexive signed graphs. We also provide several tools for reducing the problem to the bipartite case, and prove a full complexity dichotomy for a related problem.
Abstract
We make advances towards a structural characterisation of the signed graphs H for which the list switch H-colouring problem List-S-Hom(H) can be solved in polynomial time. We conjecture two different characterisations, the second refining the first, in the case that the graph H can be switched to a graph in which every negative edge is also positive. Using a recent proof of the first characterisations for reflexive signed graphs, by Bok et. al., we prove the second characterisation for reflexive signed graphs. We also provide several tools for reducing the problem to the bipartite case, and prove a full complexity dichotomy for a related problem.
참고문헌 (17)
- J. Bok, "List homomorphism problems for signed trees", Discrete Math, 346(3), pp.113257~ (2023)[DOI]
- J. Bok, "Min orderings and list homomorphism dichotomies for signed and unsigned graphs", ~ (2022)
- R. Brewster, "The complexity of signed graph and edge-coloured graph homomorphisms", Discrete Math, 340(2), pp.223~235 (2017)
- R. Brewster, "A complexity dichotomy for signed H-colouring", Discrete Math, 341, pp.2768~2773 (2018)[DOI]
- A. Bulatov, "Complexity of conservative constraint satisfaction problems", ACM Trans. Comput. Log, 12(4), pp.66~ (2011)[DOI]
- A. Bulatov, "A dichotomy theorem for nonuniform CSPs", 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, pp.319~330 (2017)
- T. Feder, "List homomorphisms to reflexive graphs", J. Combin. Theory Ser. B, 72(2), pp.236~250 (1998)[DOI]
- T. Feder, "Bi-arc graphs and the complexity of list homomorphisms", J. of Graph Theory, 42(1), pp.61~80 (2003)[DOI]
- T. Feder, "The computational structure of monotone monadic SNP and constraint satisfaction : a study through Datalog and group theory", SIAM J. Comput, 28(1), pp.57~104 (1999)[DOI]
- F. Foucaud, "The complexity of homomorphisms of signed graphs and signed constraint satisfaction", LNCS, 79(8392), pp.526~537 (2014)
- F. Harary, "On the notion of balance of a signed graph", Michigan Mathematical Journal, 2(2), pp.143~146 (1953)[DOI]
- P. Hell, "Interval-like graphs and digraphs", 43rd International Symposium on Mathematical Foundations of Computer Science, 68, pp.1~13 (2018)
- P. Hell, "On the complexity of H-coloring", J. Combin. Theory Ser. B, 48(1), pp.92~110 (1990)[DOI]
- P. Hell, "The dichotomy of list homomorphisms for digraphs", ~ (2010)
- R. Naserasr, "Homomorphisms of signed graphs", J. Graph Theory, 79(3), pp.178~212 (2015)[DOI]
- T. Zaslavsky, "Signed graphs", Discrete Applied Mathematics, 4(1), pp.47~74 (1982)[DOI]
- D. Zhuk, "A proof of the CSP dichotomy conjecture", J. ACM, 67(5), pp.78~ (2020)[DOI]