Publications in the heart of the project

Published or accepted

• Dibyayan Chakraborty, Florent Foucaud and Anni Hakanen. Distance-based covering problems for graphs of given cyclomatic number. Proceedings of the 24th International Symposium on Fundamentals of Computation Theory (FCT 2023). Lecture Notes in Computer Science 14292:132-146, 2023. [HAL | www]
• Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud and Yann Vaxès. Isometric path complexity of graphs. Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Leibniz International Proceedings in Informatics 272,32:1-32:14, 2023. [HAL |arXiv (full version) | www]
• Antoine Dailly, Florent Foucaud and Anni Hakanen. Algorithms and hardness for Metric Dimension on digraphs. Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023). Lecture Notes in Computer Science 14093:232-245, 2023. [HAL | www]
• Claire Hilaire and Jean-Florent Raymond. Long induced paths in minor-closed graph classes and beyond. The Electronic Journal of Combinatorics P1.18, 2023. [arXiv | www]
• Henning Fernau, Florent Foucaud, Kevin Mann, Utkarsh Padariya and Rajath Rao K.N.. Parameterizing path partitions. Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC 2023), Lecture Notes in Computer Science 13898:187-201, 2023. [arXiv (full version) | www]
• Sandip Das, Florent Foucaud, Sk Samim Islam and Joydeep Mukherjee. Relation between broadcast domination and multipacking numbers on chordal graphs. Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:297-308, 2023. [HAL | www]
• Florent Foucaud, Krishna Narayanan and Lekshmi R S. Monitoring edge-geodetic sets in graphs. Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:245-256, 2023. [HAL | arXiv | www]
• Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat and Subir Kumar Ghosh. Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond. Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics 248,12:1-12:17, 2022. [HAL (full version) | www]
• Maël Dumas, Florent Foucaud, Anthony Perez and Ioan Todinca. On graphs coverable by k shortest paths. Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics 248,40:1-40:15, 2022. [HAL | arXiv (full version) | www]
  

Submitted

• Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma and Prafullkumar Tale. Tight (double) exponential bounds for NP-complete problems: treewidth and vertex cover parameterizations. Manuscript, 2023. [arXiv]
  
• Oscar Defrain and Jean-Florent Raymond. Sparse graphs without long induced paths. Manuscript, 2023. [HAL | arXiv]
• Anni Hakanen and Ismael G. Yero. Complexity and equivalency of multiset dimension and ID-colorings. Manuscript, 2023. [HAL | arXiv]
• Maël Dumas, Florent Foucaud, Anthony Perez and Ioan Todinca. On graphs coverable by k shortest paths. Manuscript, 2023. [arXiv]
• Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat and Dimitri Lajou. Algorithms and complexity for geodetic sets on interval and chordal graphs. Manuscript, 2022.
  
• Anni Hakanen, Ville Junnila, Tero Laihonen and Ismael G. Yero. On the unicyclic graphs having vertices that belong to all their (strong) metric bases. Manuscript, 2022. [HAL | arXiv]

Publications close to the project

Published or accepted

• Jan Bok, Jiri Fiala, Nikola Jedlicková, Jan Kratochvil, and Michaela Seifrtova. Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two. Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023). Lecture Notes in Computer Science 14093:101-115, 2023. [www]
• Dipayan Chakraborty and Sandeep RB. Contracting edges to destroy a pattern: A complexity study. Proceedings of the 24th International Proceedings of the 24th International Symposium on Fundamentals of Computation Theory (FCT 2023). Lecture Notes in Computer Science 14292:132-146, 2023. [arXiv | www]
• Dipayan Chakraborty, Florent Foucaud, and Tuomo Lehtilä. Identifying codes in bipartite graphs of given maximum degree. Proceedings of the 12th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023), Procedia Computer Science 223(2):157-165, 2023. [HAL | www]
• Florent Foucaud, Narges Ghareghani and Pouyeh Sharifani. Extremal digraphs for open neighbourhood location-domination and identifying codes. Discrete Applied Mathematics, accepted. [arXiv]
• Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä and Aline Parreau. Neighbourhood complexity of graphs of bounded twin-width. European Journal of Combinatorics 115:103772, 2024. [PDF | arXiv | HAL | www]
• Virginia Ardévol Martínez, Marco Caoduro, Laurent Feuilloley, Jonathan Narboni, Pegah Pournajafi and Jean-Florent Raymond. Lower Bound for Constant-Size Local Certification. Theoretical Computer Science 971:114068, 2023. [HAL | www]
• Sanjana Dey, Florent Foucaud, Subhas C. Nandy and Arunabha Sen. Complexity and approximation for discriminating and identifying code problems in geometric setups. Algorithmica 85(7):1850-1882, 2023. [arXiv | HAL | www]
• Florent Foucaud and Tuomo Lehtilä. Bounds and extremal graphs for total dominating identifying codes. The Electronic Journal of Combinatorics 30(3):P3.15, 2023. [arXiv | HAL | www]
  
• Subhadeep R. Dev, Sanjana Dey, Florent Foucaud, Ralf Klasing and Tuomo Lehtilä. The RED-BLUE SEPARATION problem on graphs. Theoretical Computer Science 970:114061, 2023. [arXiv | HAL | www]
• Dipayan Chakraborty, Soumen Nandi, Sagnik Sen and Supraja D K. A linear algorithm for radio k-coloring powers of paths having small diameter. Proceedings of the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), Lecture Notes in Computer Science 13889:148-159, 2023. [www]
• Dipayan Chakraborty, Florent Foucaud, Aline Parreau and Annegret K. Wagler. On three domination-based identification problems in block graphs. Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:271-283, 2023. [HAL | arXiv (full version) | www]
• Dipayan Chakraborty, Florent Foucaud, Soumen Nandi, Sagnik Sen and Supraja D K. New bounds and constructions for neighbor-locating colorings of graphs. Proceedings of the 9th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2023), Lecture Notes in Computer Science 13947:121-133, 2023. [HAL | www]
• Florent Foucaud. Problems related to a conjecture on location-domination in twin-free graphs. Indian Journal of Discrete Mathematics 8(1):39-41, 2022. [HAL | www]
  
• Virginia Ardévol Martínez, Marco Caoduro, Laurent Feuilloley, Jonathan Narboni, Pegah Pournajafi and Jean-Florent Raymond. Lower Bound for Constant-Size Local Certification. Proceedings of the 24th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2022), Lecture Notes in Computer Science 13751:239-253, 2022. [HAL | www]
• Caroline Brosse, Vincent Limouzy and Arnaud Mary. Polynomial delay algorithm for minimal chordal completions.
  Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Leibniz International Proceedings in Informatics (LIPIcs) 229, 33:1-33:16, 2022. [arXiv | www]
• Subhadeep R. Dev, Sanjana Dey, Florent Foucaud, Ralf Klasing and Tuomo Lehtilä. The Red-Blue Separation problem on graphs.
  Proceeedings of the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022), Lecture Notes in Computer Science 13270:285-298, 2022. [HAL | www]
• Florent Foucaud and Tuomo Lehtilä. Revisiting and improving upper bounds for identifying codes. SIAM Journal on Discrete Mathematics 36(4):2619-2634, 2022. [HAL | arXiv | www]
  

Submitted

• Jan Bok, Jiri Fiala, Nikola Jedlickova, Jan Kratochvil, and Michaela Seifrtova. Computational Complexity of Covering Disconnected Multigraphs. Manuscript, 2023. [arXiv]
• Jan Bok, Jiri Fiala, Petr Hlineny, Nikola Jedlickova and Jan Kratochvil. Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases. Manuscript, 2023.
• Gaétan Berthe, Marin Bougeret, Daniel Gonçalves and Jean-Florent Raymond. Subexponential parameterized algorithms for cycle-hitting problems in contact and intersection graphs of segments. Manuscript, 2023. [arXiv]
• Caroline Brosse, Aurélie Lagoutte, Vincent Limouzy, Arnaud Mary and Lucas Pastor. Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes. Manuscript, 2023. [arXiv | HAL]
• Dipayan Chakraborty, Florent Foucaud, Aline Parreau and Annegret K. Wagler. On three domination-based identification problems in block graphs. Manuscript, 2023. [HAL | arXiv]
• Dipayan Chakraborty, Florent Foucaud, Anni Hakanen, Michael A. Henning and Annegret K. Wagler. Progress towards the two-thirds conjecture on locating-total dominating sets. Manuscript, 2022. [HAL | arXiv]

Acknowledgement sentence: "This research was supported by the ANR project GRALMECO (ANR-21-CE48-0004)."