Papers

See my profiles on dblp and Google Scholar.

Theses

• G. Paesani, Graph Transversals for Hereditary Graph Classes: a Complexity Perspective .
• G. Paesani, The relationship between the chromatic number of a graph and clique immersion.
• G. Paesani, Analogies between Zariski topology and a topology defined upon logical formulas.

Journal Papers

• G. Paesani, D. Paulusma and P. Rzazewski, Classifying Subset Feedback Vertex Set for H-free graphs, Theoretical Computer Science, (2024) to appear.
• K.K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma and V. Zamaraev, On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal, European Journal of Combinatorics, (2023) 103821.
• G. Paesani, D. Paulusma and P. Rzazewski, Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs, SIAM Journal on Discrete Mathematics, 36:4 (2022) 2453-2472.
• N. Brettel, M. Johnson, G. Paesani and D. Paulusma, Computing Subset Transversals in H-Free Graphs, Theoretical Computer Science, 902 (2022) 76-92.
• N. Brettel, J. Horsfield, A. Munaro, G. Paesani and D. Paulusma, Bounding the Mim-Width of Hereditary Graph Classes, Journal of Graph Theory, 99:1 (2022) 117-151.
• H. Bodlaender, N. Brettel, M. Johnson, E.J. Leeuwen, G. Paesani and D. Paulusma, Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective, Theoretical Computer Science, 867 (2021) 30-39.
• K.K. Dabrowski, C. Feghali, M. Johnson, G. Paesani, D. Paulusma and P. Rzazewski, On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest, Algorithmica, 82 (2020) 2841-2866.
• M. Johnson, G. Paesani and D. Paulusma, Connected Vertex Cover for (sP1+P5)-Free Graphs, Algorithmica, 82 (2020) 20-40.

Conference Papers

• R. Ganian, H. Muller, S. Ordyniak, G. Paesani, M. Rychlicki, A Tight Subexponential-time Algorithm for Two-Page Book Embedding, Proceedings of the 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2024), Tallin, Estonia, July 8-12, 2024, to appear.
• S. Ordyniak, G. Paesani, M. Rychlicki, S. Szeider, A General Theoretical Framework for Learning Smallest Interpretable Models, Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), Vancuver, Canada, February 20-27, 2024, 38(9):10662--10669.
• K.K. Dabrowski, E. Eiben, S. Ordyniak, G. Paesani, S. Szeider, Learning Small Decision Trees for Data of Low Rank-Width Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), Vancuver, Canada, February 20-27, 2024, 38(9):10476--10483.
• S. Ordyniak, G. Paesani, S. Szeider, The Parametrized Complexity of Finding Concise Local Explanations, Proceedings of the 32nd International Joint Conference on Artificial Intellingence (IJCAI 2023), Macao, China SAR, August 19-25, 2023,3312--3320.
• E. Eiben, S. Ordyniak, G. Paesani, S. Szeider, Learning Small Decision Trees with Large Domain, Proceedings of the 32nd International Joint Conference on Artificial Intellingence (IJCAI 2023), Macao, China SAR, August 19-25, 2023,3184--3192.
• G. Paesani, D. Paulusma and P. Rzazewski, Classifying Subset Feedback Vertex Set for H-free graphs, Proceedings of the 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), Tubingen, Germany, June 22-24, 2022, Lecture Notes in Computer Science, 13453:412--424.
• G. Paesani, D. Paulusma and P. Rzazewski, Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), Tallin, Estonia, August 23-27, 2021, Leibniz International Proceedings in Informatics 202, 82:1-14.
• N. Brettel, J. Horsfield, A. Munaro, G. Paesani and D. Paulusma, Bounding the Mim-Width of Hereditary Graph Classes, Proceeding of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Hong Kong, China, December 14-18, 2020, Leibniz International Proceedings in Informatics 180, 6:1-18.
• N. Brettel, M. Johnson, G. Paesani and D. Paulusma, Computing Subset Transversals in H-Free Graphs, Proceeding of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), Leeds, UK, June 24-26, 2020, Springer LNCS Proceedings, 12301:187-199.
• H. Bodlaender, N. Brettel, M. Johnson, G. Paesani, D. Paulusma and E.J. Leeuwen, Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective, Proceedings of the 14th Latin American Theoretical Informatics Symposium (LATIN 2020), São Paulo, Brasil, May 25-29, 2020, Springer LNCS Proceedings, 12118:613-624.
• K.K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma and V. Zamaraev, Independent Transversals versus Transversals, Proceedings of the 10th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2019), Bratislava, Slovakia, August 26-30, 2019, Acta Mathematica Universitatis Comenianae, 88:585-591.
• C. Feghali, M. Johnson, G. Paesani and D. Paulusma, On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest, Proceeding of the 22nd International Symposium on Fundamentals of Computation Theory (FCT 2019), Copenhagen, Denmark, August 11-14, 2019, Springer LNCS Proceedings, 11651:258-273.
• K.K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma and V. Zamaraev, On the price of independence for vertex cover, feedback vertex set and odd cycle transversal, Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Liverpool, UK, August 27-31, 2018, Leibniz International Proceedings in Informatics 117, 63:1-15.
• M. Matthew Johnson and G. Paesani and D. Paulusma, Connected Vertex Cover for (sP1+P5)-Free Graphs, Proceeding of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), Cottbus, Germany, June 27-29, 2018, Springer LNCS Proceedings, 11159:279-291.

Submitted Conference Papers

• S. Ordyniak, G. Paesani, M. Rychlicki, S. Szeider, Explaining Decisions in ML Models: a Parameterized Complexity Analysis, January 2024.