The PARAGA project is a bilateral French-Japanese research project financed under the PRCI CNRS-JSPS program. The research topic of the project is the design of algorithms for NP-hard problems on graphs, using the tools of parameterized complexity and approximation. The PARAGA project is a continuation of the GRAPA project, conducted by the same teams under the PHC Sakura program.
General Information about the project:
The project is carried out by a French and a Japanese team of researchers. Both teams include several young researchers (doctoral students/post-docs).
The project has resulted in the publication of the following research articles.
| Title: | (In)approximability of Maximum Minimal FVS |
| Author(s): | Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos |
| Conference: | ISAAC 2020 |
| Links: | draft |
| Title: | Grundy Distinguishes Treewidth from Pathwidth |
| Author(s): | Remy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi |
| Conference: | ESA 2020 |
| Links: | draft, slides, video |
| Title: | Parameterized Complexity of (A,l)-Path Packing |
| Author(s): | Remy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, and Yota Otachi |
| Conference: | IWOCA 2020 |
| Links: | draft |
| Title: | K3 Edge Cover Problem in a Wide Sense |
| Author(s): | Kyohei Chiba, Remy Belmonte, Hiro Ito, Michael Lampis, Atsuki Nagao, and Yota Otachi |
| Journal: | JIP 2020 |
| Links: | online |
| Title: | Independent Set Reconfiguration Parameterized by Modular-Width |
| Author(s): | Remy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, and Yota Otachi |
| Conference: | WG 2019 |
| Journal: | Algorithmica (2020) |
| Links: | draft |
The project's funding has allowed the two teams to organize several research workshops, giving them the opportunity to collaborate. In particular, the following research workshops have been organized as part of the PARAGA project.