Bart M. P. Jansen

Publications

My DBLP Record and Google Scholar Profile. Due to copyright restrictions, some journal articles contain improvements that are not present in the corresponding arXiv entries.

Conference publications - Journal publications - Popular science - Submissions - Theses

Conference publications

[1]

Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. “Kernelization dichotomies for hitting subgraphs under structural parameterizations”. In: Proceedings of the 51st International Colloquium on Automata, Languages and Programming, ICALP 2024. Volume 297 of Leibniz International Proceedings in Informatics (LIPIcs). 2024. doi: 10.4230/LIPIcs.ICALP.2024.33. arXiv: 2404.16695.

[2]

Benjamin Merlin Bumpus, Bart M. P. Jansen, and Jaime Venne. “Fixed-parameter tractable certified algorithms for covering and dominating in planar graphs and beyond”. In: Proceedings of the 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024. Volume 294 of LIPIcs. 2024. doi: 10.4230/LIPIcs.SWAT.2024.19.

[3]

Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan, and Ruben F.A. Verhaegh. “Preprocessing to reduce the search space for odd cycle transversal”. In: Proceedings of the 19th International Symposium on Parameterized and Exact Computation, IPEC 2024. LIPIcs. To appear. 2024. arXiv: 2409.00245.

[4]

Bart M. P. Jansen and Céline M. F. Swennenhuis. “Steiner tree parameterized by multiway cut and even less”. In: Proceedings of the 31st European Symposium on Algorithms, ESA 2024. Volume 308 of Leibniz International Proceedings in Informatics (LIPIcs). 2024, 76:1–76:16. doi: 10.4230/LIPIcs.ESA.2024.76. arXiv: 2406.19819.

[5]

Bart M. P. Jansen and Ruben F. A. Verhaegh. “Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion”. In: Proceedings of the 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024. Volume 294 of LIPIcs. 2024. doi: 10.4230/LIPIcs.SWAT.2024.28. arXiv: 2404.09769.

[6]

Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, and Kirill Simonov. “Upward and orthogonal planarity are W[1]-hard parameterized by treewidth”. In: Proceedings of the 31th International Symposium on Graph Drawing and Network Visualization, GD 2023. Volume 14466 of LNCS. 2023, pages 203–217. doi: 10.1007/978-3-031-49275-4˙14. arXiv: 2309.01264.

[7]

Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. “5-approximation for H-treewidth essentially as fast as H-deletion parameterized by solution size”. In: Proceedings of the 31st European Symposium on Algorithms, ESA 2023. Volume 274 of Leibniz International Proceedings in Informatics (LIPIcs). 2023, 66:1–66:16. doi: 10.4230/LIPIcs.ESA.2023.66. arXiv: 2306.17065.

[8]

Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. “Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classes”. In: Proceedings of the 34th International Symposium on Algorithms and Computation, ISAAC 2023. Volume 283 of LIPIcs. Extended abstract of [66]. 2023, 42:1–42:18. doi: 10.4230/LIPICS.ISAAC.2023.42. arXiv: 2309.11366.

[9]

Bart M. P. Jansen and Shivesh Roy. “On the parameterized complexity of multiway near-separator”. In: Proceedings of the 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Volume 285 of LIPIcs. 2023, 28:1–28:18. doi: 10.4230/LIPIcs.IPEC.2023.28. arXiv: 2310.04332.

[10]

Bart M. P. Jansen and Shivesh Roy. “Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs”. In: Proceedings of the 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Volume 285 of LIPIcs. 2023. doi: 10.4230/LIPIcs.IPEC.2023.29.

[11]

Bart M. P. Jansen and Bart van der Steenhoven. “Kernelization for counting problems on graphs: preserving the number of minimum solutions”. In: Proceedings of the 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Volume 285 of LIPIcs. 2023, 27:1–27:15. doi: 10.4230/LIPIcs.IPEC.2023.27. arXiv: 2310.04303.

[12]

Benjamin Merlin Bumpus, Bart M. P. Jansen, and Jari J. H. de Kroon. “Search-space reduction via essential vertices”. In: Proceedings of the 30th European Symposium on Algorithms, ESA 2022. Volume 244 of LIPIcs. Extended abstract of [67]. 2022, 30:1–30:15. doi: 10.4230/LIPIcs.ESA.2022.30. arXiv: 2207.00386.

[13]

David Dekker and Bart M. P. Jansen. “Kernelization for feedback vertex set via elimination distance to a forest”. In: Proceeding of the 48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022. Volume 13453 of LNCS. Winner of the Best Student Paper Award. Extended abstract of [68]. 2022, pages 158–172. doi: 10.1007/978-3-031-15914-5˙12. arXiv: 2206.04387.

[14]

Huib Donkers, Bart M. P. Jansen, and Jari J. H. de Kroon. “Finding k-secluded trees faster”. In: Proceeding of the 48th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2022. Volume 13453 of LNCS. Extended abstract of [72]. 2022, pages 173–186. doi: 10.1007/978-3-031-15914-5˙13. arXiv: 2206.09884.

[15]

Bart M. P. Jansen and Michal Wlodarczyk. “Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion”. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022. 2022, pages 900–913. doi: 10.1145/3519935.3520021. arXiv: 2202.02174.

[16]

Huib Donkers and Bart M. P. Jansen. “Preprocessing to reduce the search space: Antler structures for feedback vertex set”. In: Proceeding of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021. LNCS. Winner of the Best Paper and Best Student Paper Award, Extended abstract of [69]. 2021. doi: 10.1007/978-3-030-86838-3˙1. arXiv: 2106.11675.

[17]

Huib Donkers, Bart M. P. Jansen, and Michal Wlodarczyk. “Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size”. In: Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC 2021. Volume 214 of LIPIcs. Extended abstract of [76]. 2021, 14:1–14:18. doi: 10.4230/LIPIcs.IPEC.2021.14. arXiv: 2110.01868.

[18]

Bart M. P. Jansen and Jari J. H. de Kroon. “FPT algorithms to compute the elimination distance to bipartite graphs and more”. In: Proceeding of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021. LNCS. 2021. doi: 10.1007/978-3-030-86838-3˙6. arXiv: 2106.04191.

[19]

Bart M. P. Jansen, Jari J. H. de Kroon, and Michal Wlodarczyk. “Vertex deletion parameterized by elimination distance and even less”. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021. 2021, pages 1757–1769. doi: 10.1145/3406325.3451068. arXiv: 2103.09715.

[20]

Bart M. P. Jansen, Shivesh K. Roy, and Michał Włodarczyk. “On the hardness of compressing weights”. In: Proceeding of the 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021. Volume 202 of Leibniz International Proceedings in Informatics (LIPIcs). 2021, 64:1–64:21. doi: 10.4230/LIPIcs.MFCS.2021.64.

[21]

Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. “Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel”. In: Proceedings of the 47th International Colloquium on Automata, Languages and Programming, ICALP 2020. Volume 168 of Leibniz International Proceedings in Informatics (LIPIcs). Extended abstract of [75]. 2020, 16:1–16:19. doi: 10.4230/LIPIcs.ICALP.2020.16. arXiv: 2004.12865.

[22]

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Pawel Rzazewski. “Sparsification lower bounds for list H-coloring”. In: Proceedings of the 31st International Symposium on Algorithms and Computation, ISAAC 2020. Extended abstract of [71]. 2020, 58:1–58:17. doi: 10.4230/LIPIcs.ISAAC.2020.58. arXiv: 2009.08353.

[23]

Bart M. P. Jansen. “Crossing paths with Hans Bodlaender: A personal view on cross-composition for sparsification lower bounds”. In: Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Volume 12160 of LNCS. 2020, pages 89–111. doi: 10.1007/978-3-030-42071-0˙8.

[24]

Bart M. P. Jansen and Jari J. H. de Kroon. “Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies”. In: Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020. Volume 162 of Leibniz International Proceedings in Informatics (LIPIcs). Extended abstract of [77]. 2020, 27:1–27:15. doi: 10.4230/LIPIcs.SWAT.2020.27. arXiv: 2004.08818.

[25]

Bart M. P. Jansen and Michal Wlodarczyk. “Optimal polynomial-time compression for Boolean Max CSP”. In: Proceedings of the 28th European Symposium on Algorithms, ESA 2020. Volume 173 of Leibniz International Proceedings in Informatics (LIPIcs). Extended abstract of [70]. 2020, 63:1–63:19. doi: 10.4230/LIPIcs.ESA.2020.63. arXiv: 2002.03443.

[26]

Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Lukasz Kowalik. “Fine-grained complexity of k-OPT in bounded-degree graphs for solving TSP”. In: Proceedings of the 27th European Symposium on Algorithms, ESA 2019. Volume 144 of Leibniz International Proceedings in Informatics (LIPIcs). 2019, 23:1–23:14. doi: 10.4230/LIPIcs.ESA.2019.23. arXiv: 1908.09325.

[27]

Huib Donkers and Bart M. P. Jansen. “A Turing kernelization dichotomy for structural parameterizations of F-minor-free deletion”. In: Proceeding of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019. Volume 11789 of LNCS. Extended abstract of [16]. 2019, pages 106–119. doi: 10.1007/978-3-030-30786-8˙9. arXiv: 1906.05565.

[28]

Bart M. P. Jansen, László Kozma, and Jesper Nederlof. “Hamiltonicity below Dirac’s condition”. In: Proceeding of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019. Volume 11789 of LNCS. 2019, pages 27–39. doi: 10.1007/978-3-030-30786-8˙3. arXiv: 1902.01745.

[29]

Bart M. P. Jansen, Marcin Pilipczuk, and Erik Jan van Leeuwen. “A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs”. In: Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019. Volume 126 of LIPIcs. Extended abstract of [80]. 2019, 39:1–39:18. doi: 10.4230/LIPIcs.STACS.2019.39. arXiv: 1810.01136.

[30]

Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse. “Best-case and worst-case sparsifiability of Boolean CSPs”. In: Proceedings of the 13th International Symposium on Parameterized and Exact Computation, IPEC 2018. Volume 115 of LIPIcs. Extended abstract of [82]. 2018, 15:1–15:13. doi: 10.4230/LIPIcs.IPEC.2018.15. arXiv: 1809.06171.

[31]

Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel. “Lower bounds for dynamic programming on planar graphs of bounded cutwidth”. In: Proceedings of the 13th International Symposium on Parameterized and Exact Computation, IPEC 2018. Volume 115 of LIPIcs. 2018, 3:1–3:14. doi: 10.4230/LIPIcs.IPEC.2018.3. arXiv: 1806.10513.

[32]

Bart M. P. Jansen and Jesper Nederlof. “Computing the chromatic number using graph decompositions via matrix rank”. In: Proceedings of the 26th European Symposium on Algorithms, ESA 2018. Volume 112 of LIPIcs. Extended abstract of [86]. 2018, 47:1–47:15. doi: 10.4230/LIPIcs.ESA.2018.47. arXiv: 1806.10501.

[33]

Bart M. P. Jansen and Astrid Pieterse. “Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations”. In: Proceedings of the 26th European Symposium on Algorithms, ESA 2018. Volume 112 of LIPIcs. Extended abstract of [85]. 2018, 48:1–48:15. doi: 10.4230/LIPIcs.ESA.2018.48. arXiv: 1804.08885.

[34]

Lars Jaffke and Bart M. P. Jansen. “Fine-grained parameterized complexity analysis of graph coloring problems”. In: Proceedings of the 10th International Conference on Algorithms and Complexity, CIAC 2017. Volume 10236 of LNCS. Extended abstract of [74]. 2017, pages 345–356. doi: 10.1007/978-3-319-57586-5˙29. arXiv: 1701.06985.

[35]

Bart M. P. Jansen and Astrid Pieterse. “Optimal data reduction for graph coloring using low-degree polynomials”. In: Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Volume 89 of LIPIcs. Winner of the ‘Best Student Paper Award’, for the best paper with at most one graduated author. Extended abstract of [87]. 2017, 22:1–22:12. doi: 10.4230/LIPIcs.IPEC.2017.22.

[36]

Bart M. P. Jansen and Marcin Pilipczuk. “Approximation and kernelization for chordal vertex deletion”. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Extended abstract of [91]. 2017, pages 1399–1418. doi: 10.1137/1.9781611974782.91. arXiv: 1605.03001.

[37]

Bart M. P. Jansen, Marcin Pilipczuk, and Marcin Wrochna. “Turing kernelization for finding long paths in graph classes excluding a topological minor”. In: Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Volume 89 of LIPIcs. Extended abstract of [89]. 2017, 23:1–23:13. doi: 10.4230/LIPIcs.IPEC.2017.23. arXiv: 1707.01797.

[38]

Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard Woeginger. “Fine-grained complexity analysis of two classic TSP variants”. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Volume 55 of Leibniz International Proceedings in Informatics (LIPIcs). Extended abstract of [78]. 2016, 5:1–5:14. doi: 10.4230/LIPIcs.ICALP.2016.5. arXiv: 1607.02725.

[39]

Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee. “Independent-set reconfiguration thresholds of hereditary graph classes”. In: Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS. Volume 65 of LIPIcs. Extended abstract of [90]. 2016, 34:1–34:15. doi: 10.4230/LIPIcs.FSTTCS.2016.34. arXiv: 1610.03766.

[40]

Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. “The first parameterized algorithms and computational experiments challenge”. In: Proceedings of the 11th International Symposium on Parameterized and Exact Computation, IPEC 2016. Volume 63 of LIPIcs. 2016, 30:1–30:9. doi: 10.4230/LIPIcs.IPEC.2016.30.

[41]

Bart M. P. Jansen. “Constrained bipartite vertex cover: The easy kernel is essentially tight”. In: Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science, STACS 2016. Volume 47 of Leibniz International Proceedings in Informatics (LIPIcs). 2016, 45:1–45:13. doi: 10.4230/LIPIcs.STACS.2016.45.

[42]

Bart M. P. Jansen. “On structural parameterizations of hitting set: Hitting paths in graphs using 2-SAT”. In: Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015. Extended abstract of [93]. 2016, pages 472–486. doi: 10.1007/978-3-662-53174-7˙33. arXiv: 1507.05890.

[43]

Bart M. P. Jansen and Astrid Pieterse. “Optimal sparsification for some binary CSPs using low-degree polynomials”. In: Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. Volume 58 of Leibniz International Proceedings in Informatics (LIPIcs). Best paper award winner. Extended abstract of [88]. 2016, 71:1–71:14. doi: 10.4230/LIPIcs.MFCS.2016.71. arXiv: 1606.03233.

[44]

Bart M. P. Jansen and Jules J. M. Wulms. “Lower bounds for protrusion replacement by counting equivalence classes”. In: Proceedings of the 11th International Symposium on Parameterized and Exact Computation, IPEC 2016. Volume 63 of LIPIcs. Extended abstract of [84]. 2016, 17:1–17:12. doi: 10.4230/LIPIcs.IPEC.2016.17. arXiv: 1609.09304.

[45]

Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. “Uniform kernelization complexity of hitting forbidden minors”. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015. Volume 9134 of LNCS. Extended abstract of [92]. 2015, pages 629–641. doi: 10.1007/978-3-662-47672-7˙51. arXiv: 1502.03965.

[46]

Bart M. P. Jansen and Stefan Kratsch. “A structural approach to kernels for ILPs: Treewidth and total unimodularity”. In: Proceedings of the 23rd European Symposium on Algorithms, ESA 2015. Volume 9294 of LNCS. 2015, pages 779–791. doi: 10.1007/978-3-662-48350-3˙65. arXiv: 1506.07729.

[47]

Bart M. P. Jansen and Dániel Marx. “Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels”. In: Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. 2015, pages 616–629. doi: 10.1137/1.9781611973730.42. arXiv: 1410.0855.

[48]

Bart M. P. Jansen and Astrid Pieterse. “Sparsification upper and lower bounds for graph problems and not-all-equal SAT”. In: Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. Volume 43 of LIPIcs. Extended abstract of [95]. 2015, pages 163–174. doi: 10.4230/LIPIcs.IPEC.2015.163. arXiv: 1509.07437.

[49]

Bart M. P. Jansen. “Turing kernelization for finding long paths and cycles in restricted graph classes”. In: Proceedings of the 22nd European Symposium on Algorithms, ESA 2014. Volume 8737 of LNCS. Extended abstract of [94]. 2014, pages 579–591. doi: 10.1007/978-3-662-44777-2˙48. arXiv: 1402.4718.

[50]

Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. “A near-optimal planarization algorithm”. In: Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. 2014, pages 1802–1811. doi: 10.1137/1.9781611973402.130.

[51]

Michael R. Fellows and Bart M. P. Jansen. “FPT is characterized by useful obstruction sets”. In: Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013. Volume 8165 of LNCS. Extended abstract of [98]. 2013, pages 261–273. doi: 10.1007/978-3-642-45043-3˙23. arXiv: 1305.3102.

[52]

Bart M. P. Jansen. “On sparsification for computing treewidth”. In: Proceedings of the 8th International Symposium on Parameterized and Exact Computation, IPEC 2013. Volume 8246 of LNCS. Excellent Student Paper Award Winner. Extended abstract of [96]. 2013, pages 216–229. doi: 10.1007/978-3-319-03898-8˙19. arXiv: 1308.3665.

[53]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Kernel bounds for structural parameterizations of pathwidth”. In: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012. Volume 7357 of LNCS. 2012, pages 352–363. doi: 10.1007/978-3-642-31155-0˙31. arXiv: 1207.4900.

[54]

Fedor V. Fomin, Bart M. P. Jansen, and Michal Pilipczuk. “Preprocessing subgraph and minor problems: When does a small vertex cover help?” In: Proceedings of the 7th International Symposium on Parameterized and Exact Computation, IPEC 2012. Volume 7535 of LNCS. Extended abstract of [99]. 2012, pages 97–108. doi: 10.1007/978-3-642-33293-7˙11. arXiv: 1206.4912.

[55]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Cross-composition: A new technique for kernelization lower bounds”. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. Volume 9 of LIPIcs. Open Access, Extended abstract of [97]. 2011, pages 165–176. doi: 10.4230/LIPIcs.STACS.2011.165. arXiv: 1011.4224.

[56]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Kernel bounds for path and cycle problems”. In: Proceedings of the 6th International Symposium on Parameterized and Exact Computation, IPEC 2011. Volume 7112 of LNCS. Extended abstract of [101]. 2011, pages 145–158. doi: 10.1007/978-3-642-28050-4˙12. arXiv: 1106.4141.

[57]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Preprocessing for treewidth: A combinatorial analysis through kernelization”. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011. Volume 6755 of LNCS. Extended abstract of [102]. 2011, pages 437–448. doi: 10.1007/978-3-642-22006-7˙37. arXiv: 1104.4217.

[58]

Pinar Heggernes, Pim van ’t Hof, Bart M. P. Jansen, Stefan Kratsch, and Yngve Villanger. “Parameterized complexity of vertex deletion into perfect graph classes”. In: Proceedings of the 18th International Symposium on Fundamentals of Computation Theory, FCT 2011. Volume 6914 of LNCS. Extended abstract of [104]. 2011, pages 240–251. doi: 10.1007/978-3-642-22953-4˙21.

[59]

Bart M. P. Jansen and Hans L. Bodlaender. “Vertex cover kernelization revisited: Upper and lower bounds for a refined parameter”. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. Volume 9 of LIPIcs. Open Access, Extended abstract of [105]. 2011, pages 177–188. doi: 10.4230/LIPIcs.STACS.2011.177. arXiv: 1012.4701.

[60]

Bart M. P. Jansen and Stefan Kratsch. “Data reduction for graph coloring problems”. In: Proceedings of the 18th International Symposium on Fundamentals of Computation Theory, FCT 2011. Volume 6914 of LNCS. Extended Abstract of [106]. 2011, pages 90–101. doi: 10.1007/978-3-642-22953-4˙8. arXiv: 1104.4229.

[61]

Bart M. P. Jansen and Stefan Kratsch. “On polynomial kernels for structural parameterizations of odd cycle transversal”. In: Proceedings of the 6th International Symposium on Parameterized and Exact Computation, IPEC 2011. Volume 7112 of LNCS. 2011, pages 132–144. doi: 10.1007/978-3-642-28050-4˙11. arXiv: 1107.3658.

[62]

Michael R. Fellows, Bart M. P. Jansen, Daniel Lokshtanov, Frances A. Rosamond, and Saket Saurabh. “Determining the winner of a Dodgson election is hard”. In: Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010. Volume 8 of LIPIcs. Open Access. 2010, pages 459–468. doi: 10.4230/LIPIcs.FSTTCS.2010.459.

[63]

Bart M. P. Jansen. “Kernelization for maximum leaf spanning tree with positive vertex weights”. In: Proceedings of the 7th International Conference on Algorithms and Complexity, CIAC 2010. Volume 6078 of LNCS. Extended abstract of [107]. 2010, pages 192–203. doi: 10.1007/978-3-642-13073-1˙18.

[64]

Bart M. P. Jansen. “Polynomial kernels for hard problems on disk graphs”. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010. Volume 6139 of LNCS. 2010, pages 310–321. doi: 10.1007/978-3-642-13731-0˙30. url: https://www.win.tue.nl/~bjansen/papers/DiskGraphsPreprint.pdf.

[65]

Boris Aronov, Kevin Buchin, Maike Buchin, Bart M. P. Jansen, T. de Jong, Marc J. van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira, and Bettina Speckmann. “Feed-links for network extensions”. In: Proceedings of the 16th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2008. Extended abstract of [108]. 2008, pages 1–9. doi: 10.1145/1463434.1463478.

Journal publications

[66]

Bart M.P. Jansen, Jari J.H. de Kroon, and Michal Wlodarczyk. “Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classes”. In: Journal of Computer and System Sciences 148, 2025, page 103597. doi: 10.1016/j.jcss.2024.103597.

[67]

Benjamin Merlin Bumpus, Bart M. P. Jansen, and Jari J. H. de Kroon. “Search-space reduction via essential vertices”. In: SIAM Journal on Discrete Mathematics 38(3), 2024, pages 2392–2415. doi: 10.1137/23M1589347.

[68]

David J.C. Dekker and Bart M.P. Jansen. “Kernelization for feedback vertex set via elimination distance to a forest”. In: Discrete Applied Mathematics 346, 2024, pages 192–214. doi: 10.1016/j.dam.2023.12.016. arXiv: 2206.04387.

[69]

Huib Donkers and Bart M.P. Jansen. “Preprocessing to reduce the search space: antler structures for feedback vertex set”. In: Journal of Computer and System Sciences 144, 2024. doi: 10.1016/j.jcss.2024.103532.

[70]

Bart M. P. Jansen and Michał Włodarczyk. “Optimal polynomial-time compression for Boolean Max CSP”. In: ACM Transactions on Computation Theory 16(1), 2024. doi: 10.1145/3624704.

[71]

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Pawel Rzazewski. “Sparsification lower bounds for list H-coloring”. In: ACM Transactions on Computation Theory 15(3–4), 2023. doi: 10.1145/3612938. arXiv: 2009.08353.

[72]

Huib Donkers, Bart M. P. Jansen, and Jari J. H. de Kroon. “Finding k-secluded trees faster”. In: Journal of Computer and System Sciences 138, 103461 2023. doi: 10.1016/j.jcss.2023.05.006. arXiv: 2206.09884.

[73]

Carl Einarson, Gregory Z. Gutin, Bart M. P. Jansen, Diptapriyo Majumdar, and Magnus Wahlström. “p-edge/vertex-connected vertex cover: parameterized and approximation algorithms”. In: J. Comput. Syst. Sci. 133, 2023, pages 23–40. doi: 10.1016/j.jcss.2022.11.002.

[74]

Lars Jaffke and Bart M. P. Jansen. “Fine-grained parameterized complexity analysis of graph coloring problems”. In: Discret. Appl. Math. 327, 2023, pages 33–46. doi: 10.1016/j.dam.2022.11.011.

[75]

Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau. “Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel”. In: SIAM Journal on Discrete Mathematics 36(4), 2022, pages 2737–2773. doi: 10.1137/21M1400766. arXiv: 2004.12865.

[76]

Huib Donkers, Bart M. P. Jansen, and Michal Wlodarczyk. “Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size”. In: Algorithmica 84(11), 2022. IPEC 2021 Special Issue, pages 3407–3458. doi: 10.1007/s00453-022-00984-2. arXiv: 2110.01868.

[77]

Bart M. P. Jansen and Jari J. H. de Kroon. “Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies”. In: Journal of Computer and System Sciences 126, 2022, pages 59–79. doi: 10.1016/j.jcss.2021.12.003. arXiv: 2004.08818.

[78]

Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard J. Woeginger. “Fine-grained complexity analysis of two classic TSP variants”. In: ACM Trans. Algorithms 17(1), 2021, 5:1–5:29. doi: 10.1145/3414845.

[79]

Huib Donkers and Bart M. P. Jansen. “A Turing kernelization dichotomy for structural parameterizations of F-minor-free deletion”. In: J. Comput. Syst. Sci. 119, 2021, pages 164–182. doi: 10.1016/j.jcss.2021.02.005.

[80]

Bart M. P. Jansen, Marcin Pilipczuk, and Erik Jan van Leeuwen. “A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs”. In: SIAM J. Discret. Math. 35(4), 2021, pages 2387–2429. doi: 10.1137/20M1353782.

[81]

Bart M. P. Jansen and Jan Arne Telle. “Special issue dedicated to the 14th international symposium on parameterized and exact computation”. In: Algorithmica 83(8), 2021. Editor’s foreword, pages 2469–2470. doi: 10.1007/s00453-021-00853-4.

[82]

Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse. “Best-case and worst-case sparsifiability of Boolean CSPs”. In: Algorithmica 82(8), 2020, pages 2200–2242. doi: 10.1007/s00453-019-00660-y. arXiv: 1809.06171.

[83]

Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel. “Lower bounds for dynamic programming on planar graphs of bounded cutwidth”. In: J. Graph Algorithms Appl. 24(3), 2020, pages 461–482. doi: 10.7155/jgaa.00542.

[84]

Bart M. P. Jansen and Jules J. M. Wulms. “Lower bounds for protrusion replacement by counting equivalence classes”. In: Discrete Applied Mathematics 278, 2020. Eighth Workshop on Graph Classes, Optimization, and Width Parameters, pages 12–27. doi: 10.1016/j.dam.2019.02.024. arXiv: 1609.09304.

[85]

Bart M.P. Jansen and Astrid Pieterse. “Polynomial kernels for hitting forbidden minors under structural parameterizations”. In: Theoretical Computer Science 841, 2020, pages 124–166. doi: 10.1016/j.tcs.2020.07.009. arXiv: 1804.08885.

[86]

Bart M. P. Jansen and Jesper Nederlof. “Computing the chromatic number using graph decompositions via matrix rank”. In: Theoretical Computer Science 795, 2019, pages 520–539. doi: 10.1016/j.tcs.2019.08.006. arXiv: 1806.10501.

[87]

Bart M. P. Jansen and Astrid Pieterse. “Optimal data reduction for graph coloring using low-degree polynomials”. In: Algorithmica 81, 10 2019, pages 3865–3889. doi: 10.1007/s00453-019-00578-5. arXiv: 1802.02050.

[88]

Bart M. P. Jansen and Astrid Pieterse. “Optimal sparsification for some binary CSPs using low-degree polynomials”. In: ACM Trans. Comput. Theory 11(4), 2019, 28:1–28:26. doi: 10.1145/3349618. arXiv: 1606.03233.

[89]

Bart M. P. Jansen, Marcin Pilipczuk, and Marcin Wrochna. “Turing kernelization for finding long paths in graph classes excluding a topological minor”. In: Algorithmica 81(10), 2019, pages 3936–3967. doi: 10.1007/s00453-019-00614-4. arXiv: 1707.01797.

[90]

Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee. “Independent-set reconfiguration thresholds of hereditary graph classes”. In: Discrete Applied Mathematics 250, 2018, pages 165–182. doi: 10.1016/j.dam.2018.05.029. arXiv: 1610.03766.

[91]

Bart M. P. Jansen and Marcin Pilipczuk. “Approximation and kernelization for chordal vertex deletion”. In: SIAM Journal on Discrete Mathematics 32(3), 2018, pages 2258–2301. doi: 10.1137/17M112035X. arXiv: 1605.03001.

[92]

Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. “Uniform kernelization complexity of hitting forbidden minors”. In: ACM Transactions on Algorithms 13(3), 2017, 35:1–35:35. doi: 10.1145/3029051. arXiv: 1502.03965.

[93]

Bart M. P. Jansen. “On structural parameterizations of hitting set: Hitting paths in graphs using 2-SAT”. In: Journal of Graph Algorithms and Applications 21(2), 2017, pages 219–243. doi: 10.7155/jgaa.00413.

[94]

Bart M. P. Jansen. “Turing kernelization for finding long paths and cycles in restricted graph classes”. In: Journal of Computer and System Sciences 85, 2017, pages 18–37. doi: 10.1016/j.jcss.2016.10.008.

[95]

Bart M. P. Jansen and Astrid Pieterse. “Sparsification upper and lower bounds for graph problems and not-all-equal SAT”. In: Algorithmica 79(1), 2017. IPEC 2015 Special Issue, pages 3–28. doi: 10.1007/s00453-016-0189-9. arXiv: 1509.07437.

[96]

Bart M. P. Jansen. “On sparsification for computing treewidth”. In: Algorithmica 71(3), 2015. IPEC 2013 Special Issue, pages 605–635. doi: 10.1007/s00453-014-9924-2. arXiv: 1308.3665.

[97]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Kernelization lower bounds by cross-composition”. In: SIAM Journal on Discrete Mathematics 28(1), 2014, pages 277–305. doi: 10.1137/120880240. arXiv: 1206.5941.

[98]

Michael R. Fellows and Bart M. P. Jansen. “FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders”. In: ACM Transactions on Computation Theory 6(4), 2014, 16:1–16:26. doi: 10.1145/2635820. arXiv: 1305.3102.

[99]

Fedor V. Fomin, Bart M. P. Jansen, and Michal Pilipczuk. “Preprocessing subgraph and minor problems: When does a small vertex cover help?” In: Journal of Computer and System Sciences 80(2), 2014, pages 468–495. doi: 10.1016/j.jcss.2013.09.004.

[100]

Bart M. P. Jansen, Venkatesh Raman, and Martin Vatshelle. “Parameter ecology for feedback vertex set”. In: Tsinghua Science and Technology 19(4), 2014. Special Issue dedicated to Jianer Chen, pages 387–409. doi: 10.1109/TST.2014.6867520.

[101]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Kernel bounds for path and cycle problems”. In: Theoretical Computer Science 511, 2013. Special Issue on Parameterized and Exact Computation, pages 117–136. doi: 10.1016/j.tcs.2012.09.006. arXiv: 1106.4141.

[102]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Preprocessing for treewidth: A combinatorial analysis through kernelization”. In: SIAM Journal on Discrete Mathematics 27(4), 2013, pages 2108–2142. doi: 10.1137/120903518. arXiv: 1104.4217.

[103]

Michael R. Fellows, Bart M. P. Jansen, and Frances Rosamond. “Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity”. In: European Journal of Combinatorics 34(3), 2013. IWOCA 2009 Special Issue, pages 541–566. doi: 10.1016/j.ejc.2012.04.008. url: https://www.win.tue.nl/~bjansen/papers/EcologySurvey.pdf.

[104]

Pinar Heggernes, Pim van ’t Hof, Bart M. P. Jansen, Stefan Kratsch, and Yngve Villanger. “Parameterized complexity of vertex deletion into perfect graph classes”. In: Theoretical Computer Science 511, 2013. Special Issue on Parameterized and Exact Computation, pages 172–180. doi: 10.1016/j.tcs.2012.03.013. url: https://www.win.tue.nl/~bjansen/papers/PerfectDeletion.pdf.

[105]

Bart M. P. Jansen and Hans L. Bodlaender. “Vertex cover kernelization revisited - Upper and lower bounds for a refined parameter”. In: Theory of Computing Systems 53(2), 2013. Open Access, STACS 2011 Special Issue, pages 263–299. doi: 10.1007/s00224-012-9393-4.

[106]

Bart M. P. Jansen and Stefan Kratsch. “Data reduction for graph coloring problems”. In: Information and Computation 231(0), 2013. FCT 2011 Special Issue, pages 70–88. doi: 10.1016/j.ic.2013.08.005. arXiv: 1104.4229.

[107]

Bart M. P. Jansen. “Kernelization for maximum leaf spanning tree with positive vertex weights”. In: Journal of Graph Algorithms and Applications 16(4), 2012. Open Access, pages 811–846. doi: 10.7155/jgaa.00279.

[108]

Boris Aronov, Kevin Buchin, Maike Buchin, Bart M. P. Jansen, Tom de Jong, Marc J. van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira, and Bettina Speckmann. “Connect the dot: Computing feed-links for network extension”. In: Journal of Spatial Information Science 3(1), 2011. Open Access, pages 3–31. doi: 10.5311/JOSIS.2011.3.47.

Popular science

[109]

Bart M. P. Jansen. How to plan Valentine’s day using a matching algorithm. Popular science article on The Network Pages. 2019. url: http://www.networkpages.nl/how-to-plan-valentines-day-using-a-matching-algorithm/.

[110]

Bart M. P. Jansen. Finding the shortest route to your holiday destination: Dijkstra’s algorithm. Popular science article on The Network Pages. 2017. url: http://www.networkpages.nl/finding-the-shortest-route-to-your-holiday-destination-dijkstras-algorithm/.

[111]

De Kennis van Nu Radio (Interview). Dutch. Interview about my Ph. D. thesis after winning the Huygens Prize. Interview starts at 45:20. June 30, 2014.

[112]

Joost Hanraets and Bart M. P. Jansen. Met reductieregels grote datasets te lijf. Dutch. Interview about my Ph. D. thesis after winning the Huygens Prize. 2014.

Ph.D. Thesis

  • Bart M. P. Jansen. "The Power of Data Reduction: Kernels for Fundamental Graph Problems". Utrecht University, 2013, 310 pages, ISBN 978-90-393-5966-2, PDF, Info

Master's Thesis

  • Bart M. P. Jansen: Fixed Parameter Complexity of the Weighted Max Leaf Problem, Master Thesis INF/SCR-2008-075, Utrecht University, 2009, PDF, Info