Conference publications

Sparsification Lower Bounds for List H-Coloring

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse and Paweł Rzążewski.
Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), December 14-18, Hong Kong (virtual conference), pages 58:1-58:17, 2020.

[doi]; Full version on [arXiv].

Approximate Turing Kernelization for Problems Parameterized by Treewidth

Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse.
Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020), September 7-9, Pisa, Italy, pages 60:1-60:23, 2020.

[doi]; Full version on [arXiv].

Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse.
Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), March 10-13, 2020, Montpellier, France, pages 36:1-36:14, 2020.

[doi]; Full version on [arXiv].

Parameterized Complexity of Conflict-free Graph Coloring

Hans L. Bodlaender, Sudeshna Kolay, and Astrid Pieterse.
Proceedings of the 16th Algorithms and Data Structures Symposium (WADS 2019), August 5-7, 2019, Edmonton, Canada, pages 168-180, 2019.

[doi]; Full version on [arXiv].

Best-case and Worst-case Sparsifiability of Boolean CSPs

Hubie Chen, Bart M.P. Jansen, and Astrid Pieterse.
Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), August 20-24, 2018, Helsinki, Finland, pages 15:1-15:13, 2018.

[doi]; Full version on [arXiv].

Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations

Bart M.P. Jansen and Astrid Pieterse.
Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), August 20-22, 2018, Helsinki, Finland, pages 48:1-48:15, 2018.

[doi]; Full version on [arXiv].

The Subset Sum Game Revisited

Astrid Pieterse and Gerhard J. Woeginger.
Proceedings of the 5th International Conference on Algorithmic Decision Theory (ADT 2017), October 25-27, 2017, Luxembourg, pages 228-240, 2017.

[doi]; [BibTeX].

Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials

Bart M.P. Jansen and Astrid Pieterse.
Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), September 4-8, 2017, Vienna, pages 22:1-22:12, 2017.
Received the excellent student paper award at IPEC 2017. A paper is eligible for the Excellent student paper award if at least one co-author is a student, and at most one co-author is not a student. If there is a non-student author, the students’ contributions must be substantial, and a student must give the presentation at the conference.

[doi]; [BibTeX]; Extended version on [arXiv].

Optimal Sparsification for Some Binary CSPs Using Low-degree Polynomials

Bart M.P. Jansen and Astrid Pieterse.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), August 22-26, 2016, Krakow, Poland, pages 71:1-71:14, 2016.
Received the best paper award at MFCS 2016.

[doi]; [BibTeX]; Full version on [arXiv].

Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT

Bart M.P. Jansen and Astrid Pieterse.
Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), September 16-18, 2015, Patras, Greece, pages 163-174, 2015.

[doi]; [BibTeX]; Full version on [arXiv].

Sparsification Lower Bounds for List H-Coloring

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Pawel Rzazewski
ACM Transactions on Computation Theory, 2023.

[doi], [arXiv].

Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse
SIAM Journal on Discrete Mathematics, Volume 36, number 3, pages 1955 - 1990, 2022.

[doi].

Parameterized Complexity of Conflict-Free Graph Coloring

Hans L. Bodlaender, Sudeshna Kolay and Astrid Pieterse
SIAM Journal on Discrete Mathematics, Volume 35, number 3, pages 2003 - 2038, 2021.

[doi].

The Subset Sum Game Revisited

Astrid Pieterse and Gerhard J. Woeginger
Theory of Computing Systems, Volume 65, pages 884-900, 2021.

[doi] (Open access).

Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations

Bart M.P. Jansen and Astrid Pieterse.
Theoretical Computer Science, Volume 841, pages 124-166, 12 November 2020.

[doi].

Best-case and Worst-case Sparsifiability of Boolean CSPs

Hubie Chen, Bart M.P. Jansen, and Astrid Pieterse.
Algorithmica, 82(8): 2200-2242, 2020.

[doi], (incomplete) version on [arXiv], or see Chapter 4 of my thesis.

Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials

Bart M.P. Jansen and Astrid Pieterse.
Algorithmica 81(10): 3865-3889, October 2019.

[doi] (Open access).

Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

Bart M.P. Jansen and Astrid Pieterse.
ACM Transactions on Computation Theory, Volume 11 Issue 4, September 2019.

[doi].

Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT

Bart M.P. Jansen and Astrid Pieterse.
Algorithmica 79(1) 3-28, September 2017.

[doi] (Open access); [BibTeX].

Mosaic Drawings and Cartograms

R.G. Cano, K. Buchin, T.H.A. Castermans, A. Pieterse, W.M. Sonke, and B. Speckmann.
Computer Graphics Forum 34(3) 361-370, June 2015.

[doi]; [BibTeX].

Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT

Astrid Pieterse, supervisor: Bart M.P. Jansen, August 2015.

Download [pdf]; see also the TU/e repository.

Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials (summary)

Astrid Pieterse.
The Parameterized Complexity Newsletter, volume 13 no 3, October 2017.

This article is a summary of the main algorithmic idea in the IPEC 2017 Best Student Paper Award paper by Bart M. P. Jansen and Astrid Pieterse

Download [pdf], or see the FPT news webpage.