Document Open Access Logo

Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems

Authors Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, Théo Pierron

PDF

File

Thumbnail PDF
PDF
LIPIcs.IPEC.2019.15.pdf
  • Filesize: 0.55 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Graph homomorphism
  • Graph modification
  • Edge-coloured graph
  • Signed graph

Metrics

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

Abstract

We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from an edge-coloured graph G to an edge-coloured graph H is a vertex-mapping from G to H that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph H, which generalises the classic vertex-colourability property. The question we are interested in is the following: given an edge-coloured graph G, can we perform k graph operations so that the resulting graph admits a homomorphism to H? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs + and -. We denote the corresponding problems (parameterized by k) by Vertex Deletion-H-Colouring, Edge Deletion-H-Colouring and Switching-H-Colouring. These problems generalise the extensively studied H-Colouring problem (where one has to decide if an input graph admits a homomorphism to a fixed target H). For 2-edge-coloured H, it is known that H-Colouring already captures the complexity of all fixed-target Constraint Satisfaction Problems.
Our main focus is on the case where H is an edge-coloured graph of order at most 2, a case that is already interesting since it includes standard problems such as Vertex Cover, Odd Cycle Transversal and Edge Bipartization. For such a graph H, we give a PTime/NP-complete complexity dichotomy for all three Vertex Deletion-H-Colouring, Edge Deletion-H-Colouring and Switching-H-Colouring problems. Then, we address their parameterized complexity. We show that all Vertex Deletion-H-Colouring and Edge Deletion-H-Colouring problems for such H are FPT. This is in contrast with the fact that already for some H of order 3, unless PTime = NP, none of the three considered problems is in XP, since 3-Colouring is NP-complete. We show that the situation is different for Switching-H-Colouring: there are three 2-edge-coloured graphs H of order 2 for which Switching-H-Colouring is W[1]-hard, and assuming the ETH, admits no algorithm in time f(k)n^{o(k)} for inputs of size n and for any computable function f. For the other cases, Switching-H-Colouring is FPT.

Cite As Get BibTex

Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, and Théo Pierron. Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2019.15

Author Details

Florent Foucaud
  • Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, F-45067 Orléans Cedex 2, France
  • Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France
Hervé Hocquard
  • Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France
Dimitri Lajou
  • Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France
Valia Mitsou
  • Université Paris-Diderot, IRIF, CNRS, 75205, Paris, France
Théo Pierron
  • Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France
  • DIMEA, Masaryk University, 60200 Brno, Czech republic

Funding

This research was financed by the ANR project HOSIGRA (ANR-17-CE40-0022) and the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39).

References

  1. Z. Bawar, R. C. Brewster, and D. A. Marcotte. Homomorphism duality in edge-coloured graphs. Annales des sciences mathématiques du Québec, 29(1):21-34, 2005. Google Scholar
  2. R. C. Brewster. Vertex colourings of edge-coloured graphs. PhD thesis, Simon Fraser University, Canada, 1993. Google Scholar
  3. R. C. Brewster. The complexity of colouring symmetric relational systems. Discrete Applied Mathematics, 49(1):95-105, 1994. Google Scholar
  4. R. C. Brewster, R. Dedić, F. Huard, and J. Queen. The recognition of bound quivers using edge-coloured homomorphisms. Discrete Mathematics, 297:13-25, 2005. Google Scholar
  5. R. C. Brewster, F. Foucaud, P. Hell, and R. Naserasr. The complexity of signed and edge-coloured graph homomorphisms. Discrete Mathematics, 340(2):223-235, 2017. Google Scholar
  6. R. C. Brewster and M. H. Siggers. A complexity dichotomy for signed H-colouring. Discrete Mathematics, 341(10):2768-2773, 2018. Google Scholar
  7. A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. In IEEE Computer Society, pages 319-330, FOCS 2017, 2017. Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science. Google Scholar
  8. J. Bulín. On the complexity of H-coloring for special oriented trees. European Journal of Combinatorics, 69:54-75, 2018. Google Scholar
  9. L. Cai. Fixed parameter tractability of graph modification problem for hereditary properties. Information Processing Letters, 58:171-176, 1996. Google Scholar
  10. L. Cai. Parameterized complexity of vertex colouring. Discrete Applied Mathematics, 127:415-429, 2003. Google Scholar
  11. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  12. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. Google Scholar
  13. A. Ehrenfeucht, J. Hage, T. Harju, and G. Rozenberg. Complexity issues in switching of graphs. In Lecture Notes in Computer Science, pages 59-70, Proceedings of the International Workshop on Theory and Application of Graph Transformations, TAGT'98, 1764, 2000. Google Scholar
  14. T. Feder and M. Y. Vardi. The computational structure of monotone monadic snp and constraint satisfaction: a study through datalog and group theory. SIAM Journal on Computing, 28(1):57-104, 1998. Google Scholar
  15. M. R. Fellows, D. Hermelin, F. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 40(1):53-61, 2009. Google Scholar
  16. F. Foucaud and R. Naserasr. The complexity of homomorphisms of signed graphs and signed constraint satisfaction. In Lecture Notes in Computer Science, pages 526-537, Proceedings of the 11th Latin American Symposium on Theoretical Informatics 2014, LATIN'14. 8392, 2014. Google Scholar
  17. F. Harary. On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2):143-146, 1953-1954. Google Scholar
  18. P. Hell and J. Nešetřil. On the complexity of H-coloring. Journal of Combinatorial Theory Series B, 48(1):92-110, 1990. Google Scholar
  19. F. Hüffner, N. Betzler, and R. Niedermeier. Separator-based data reduction for signed graph balancing. Journal of Combinatorial Optimization, 20(4):335-360, 2010. Google Scholar
  20. L. Jaffke and B. M. P. Jansen. Fine-grained parameterized complexity analysis of graph coloring problems. In Lecture Notes in Computer Science, pages 345-356, Proceedings of the 10th International Conference on Algorithms and Complexity, CIAC'17. 10236, 2017. Google Scholar
  21. E. Jelínková, O. Suchý, P. Hliněný, and J. Kratochvíl. Parameterized problems related to Seidel’s switching. Discrete Mathematics and Theoretical Computer Science, 13(2):19-42, 2011. Google Scholar
  22. S. Khot and V. Raman. Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science, 289(2):997-1008, 2002. Google Scholar
  23. J. M. Lewis and M. Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. Google Scholar
  24. D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105:41-71, 2011. Google Scholar
  25. D. Marx. Parameterized coloring problems on chordal graphs. Theoretical Computer Science, 351(3):407-424, 2006. Google Scholar
  26. R. Naserasr, E. Rollová, and É. Sopena. Homomorphisms of signed graphs. Journal of Graph Theory, 79(3):178-212, 2015. Google Scholar
  27. Y. Takenaga and K. Higashide. Vertex coloring of comparability +ke and -ke graphs. In Lecture Notes in Computer Science, pages 102-112, Proceedings of the 32nd International Worksop on Graph-Theoretic Concepts in Computer Science, WG'06. 4271, 2006. Google Scholar
  28. M. Yannakakis. Edge-deletion problems. SIAM Journal on Computing, 10(2):297-309, 1981. Google Scholar
  29. T. Zaslavsky. Signed graphs. Discrete Applied Mathematics, 4(1):47-74, 1982. Google Scholar
  30. D. Zhuk. A proof of CSP dichotomy conjecture. In IEEE Computer Society, pages 331-342, FOCS 2017, 2017. Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »