Graph Algorithms

Research output

Content available in repository 2022 2022 2023 2024 2025

• 15 Conference contribution
• 13 Article
• 2 Phd Thesis 1 (Research TU/e / Graduation TU/e)
• 2 Preprint
• 1 More
  • 1 Chapter

Content available in repository

Content available in repository

Search results

• 2025

  Single-exponential FPT algorithms for enumerating secluded F-free subgraphs and deleting to scattered graph classes

  Jansen, B. M. P. (Corresponding author), de Kroon, J. J. H. & Wlodarczyk, M., Mar 2025, In: Journal of Computer and System Sciences. 148, 16 p., 103597.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File
• 2024

  Fixed-Parameter Tractable Certified Algorithms for Covering and Dominating in Planar Graphs and Beyond

  Bumpus, B. M., Jansen, B. M. P. & Venne, J., 2024, Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2024. Bodlaender, H. L. (ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vol. 294. 16 p. 19. (LIPIcs).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

• Kernelization Dichotomies for Hitting Subgraphs Under Structural Parameterizations

  Bougeret, M., Jansen, B. M. P. & Sau, I., 2024, Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024. Bringmann, K., Grohe, M., Puppis, G. & Svensson, O. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vol. 297. 20 p. 33. (LIPIcs).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

• Kernelization for feedback vertex set via elimination distance to a forest

  Dekker, D. & Jansen, B. M. P. (Corresponding author), 31 Mar 2024, In: Discrete Applied Mathematics. 346, p. 192-214 23 p.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

• Optimal Polynomial-Time Compression for Boolean Max CSP

  Jansen, B. M. P. & Wlodarczyk, M., Mar 2024, In: ACM Transactions on Computation Theory. 16, 1, 20 p., 4.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

• Parameterized Algorithms for Augmented Graph Problems

  Roy, S. K., 19 Sept 2024, Eindhoven: Eindhoven University of Technology. 174 p.

  Research output: Thesis › Phd Thesis 1 (Research TU/e / Graduation TU/e)

  Open Access

  File
  108 Downloads (Pure)

• Preprocessing to reduce the search space: Antler structures for feedback vertex set

  Donkers, H. & Jansen, B. M. P. (Corresponding author), Sept 2024, In: Journal of Computer and System Sciences. 144, 26 p., 103532.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

• Preprocessing to Reduce the Search Space for Odd Cycle Transversal

  Jansen, B. M. P., Mizutani, Y., Sullivan, B. D. & Verhaegh, R. F. A., 5 Dec 2024, 19th International Symposium on Parameterized and Exact Computation, IPEC 2024. Bonnet, É. & Rzążewski, P. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 18 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 321).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  File

  • Transversals 100%
  • Search Space 100%
  • Kernelization 33%
  • Polynomial 16%
  • Bipartite Graph 16%

• Search-Space Reduction via Essential Vertices

  Bumpus, B. M., Jansen, B. M. P. (Corresponding author) & de Kroon, J. J. H., 2024, In: SIAM Journal on Discrete Mathematics. 38, 3, p. 2392-2415 24 p.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

• Search-Space Reduction via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion

  Jansen, B. M. P. & Verhaegh, R. F. A., 31 May 2024, 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024. Bodlaender, H. L. (ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 28:1-28:17 17 p. 28. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 294).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  File

  • Polynomial Time 100%
  • Search Space 100%
  • Opts _ _ _ 50%
  • Lower and upper bounds 50%
  • Linear Program 50%

• Steiner Tree Parameterized by Multiway Cut and Even Less

  Jansen, B. M. P. & Swennenhuis, C. M. F., 2024, Proceedings of the 32nd Annual European Symposium on Algorithms, ESA 2024. Chan, T. M., Fischer, J., Iacono, J. & Herman, G. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Vol. 308. 16 p. 76. (LIPIcs).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

• The Algorithmic Complexity of the Paired Matching Problem

  Verhaegh, R. F. A., Feb 2024, 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW2023. Springer Nature, p. 1-13 13 p. (AIRO Springer Series; vol. 13).

  Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

  • Bipartite Graph 100%
  • Maximum Matching 100%
  • Exact Algorithm 100%
  • Algorithmic Complexity 100%
  • Matching Problem 100%

• Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth

  Jansen, B. M. P., Khazaliya, L. (Corresponding author), Kindermann, P., Liotta, G., Montecchiani, F. & Simonov, K., 6 Jan 2024, Graph Drawing and Network Visualization: 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 20–22, 2023, Revised Selected Papers, Part II. Bekos, M. A. & Chimani, M. (eds.). Springer, p. 203-217 15 p. (Lecture Notes in Computer Science (LNCS); vol. 14466).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  File

  • Testing Problem 100%
  • NP-completeness 50%
  • Intermediate Step 50%
  • Planar Graph 50%
  • Completeness Proof 50%
  2 Citations (Scopus)
• 2023

  5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size.

  Jansen, B. M. P., de Kroon, J. J. H. & Wlodarczyk, M., Sept 2023, 31st Annual European Symposium on Algorithms, ESA 2023. Li Gortz, I., Farach-Colton, M., Puglisi, S. J. & Herman, G. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16 p. 66. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 274).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  • Approximates 100%
  • Transversals 100%
  • Tree-Like 100%
  • Closed Graph 100%
  2 Citations (Scopus)

• A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints

  Nederlof, J., Swennenhuis, C. M. F. & Węgrzycki, K., 6 Dec 2023.

  Research output: Working paper › Preprint › Academic

  File

  • Minimizes 100%
  • Worst Case 100%
  • Running Time 100%
  • Open Problem 100%
  • Unit Length 100%
  107 Downloads (Pure)

• Finding k-secluded trees faster

  Donkers, H., Jansen, B. M. P. & de Kroon, J. J. H. (Corresponding author), Dec 2023, In: Journal of Computer and System Sciences. 138, 17 p., 103461.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

  • Directed Graphs 100%
  • Tractable Algorithm 100%
  • Double Exponential 100%
  • Open Neighbourhood 100%
  • Running Time 33%
  1 Citation (Scopus)

  52 Downloads (Pure)

• Fine-grained parameterized complexity analysis of graph coloring problems

  Jaffke, L. (Corresponding author) & Jansen, B. M. P., 15 Mar 2023, In: Discrete Applied Mathematics. 327, p. 33-46 14 p.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

  • Exponential Time 100%
  • Graph Coloring 100%
  • Simple Graph 50%
  • Vertex of a Graph 50%
  • Polynomial Time 50%
  6 Citations (Scopus)

  60 Downloads (Pure)

• Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space

  Nederlof, J., Pilipczuk, M., Swennenhuis, C. M. F. & Wegrzycki, K. (Corresponding author), 2023, In: SIAM Journal on Discrete Mathematics. 37, 3, p. 1566-1586 21 p.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

  • Polynomial 100%
  • Exponential Polynomial 100%
  • Exponential Time 100%
  • Hamiltonian Cycle 100%
  • Complexity Space 100%
  75 Downloads (Pure)

• Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions

  Jansen, B. M. P. & Steenhoven, B. V. D., Dec 2023, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Misra, N. & Wahlstrom, M. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-15 15 p. 27. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 285).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  • Future Development 100%
  • Decision Problem 100%
  • Planar Graph 100%
  • polynomial-time algorithm 100%
  • Polynomial Time 100%
  1 Citation (Scopus)

• On the Parameterized Complexity of Multiway Near-Separator

  Jansen, B. M. P. & Roy, S. K., Dec 2023, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Misra, N. & Wahlstrom, M. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 18 p. 28. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 285).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  • Approximation (Algorithm) 100%
  • Directed Graphs 100%
  • Tractable Algorithm 100%
  • polynomial-time algorithm 100%
  • Polynomial Time 100%

• Parameterized Graph Modification Beyond the Natural Parameter

  de Kroon, J. J. H., 4 Jul 2023, Eindhoven: Eindhoven University of Technology. 194 p.

  Research output: Thesis › Phd Thesis 1 (Research TU/e / Graduation TU/e)

  Open Access

  File
  392 Downloads (Pure)

• p-Edge/vertex-connected vertex cover: Parameterized and approximation algorithms

  Einarson, C., Gutin, G. Z. (Corresponding author), Jansen, B. M. P., Majumdar, D. & Wahlström, M., May 2023, In: Journal of Computer and System Sciences. 133, p. 23-40 18 p.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

  • Edge 100%
  • Approximates 33%
  • Polynomial 33%
  • Integer 16%
  • Connected Graph 16%
  1 Citation (Scopus)

  124 Downloads (Pure)

• Scheduling jobs that change over time

  Swennenhuis, C., Spieksma, F. C. R., Pendavingh, R. A. & Lambers, R., 18 Dec 2023.

  Research output: Working paper › Preprint › Academic

  • Minimizes 100%
  • Polynomial Time 50%
  • Structural Property 50%
  • Linear Program 50%
  • Arbitrary Number 50%

• Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes.

  Jansen, B. M. P., Kroon, J. J. H. D. & Wlodarczyk, M., Dec 2023, 34th International Symposium on Algorithms and Computation, ISAAC 2023. Iwata, S., Iwata, S. & Kakimura, N. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-18 18 p. 42. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 283).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  • Induced Subgraph 100%
  • Finite Set 50%
  • Positive Integer 25%
  • Exponential Time 25%
  • Connected Component 25%

• Sparsification Lower Bounds for List H-Coloring

  Chen, H., Jansen, B. M. P., Okrasa, K., Pieterse, A. & Rzążewski, P., Dec 2023, In: ACM Transactions on Computation Theory. 15, 3-4, 23 p., 8.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

  • Polynomial Time 100%
  • Directed Graphs 50%
  • Graph Coloring 50%
  • Coloring Problem 50%
  • Vertex Instance 50%
  43 Downloads (Pure)

• Sunflowers Meet Sparsity: A Linear-Vertex Kernel for Weighted Clique-Packing on Sparse Graphs

  Jansen, B. M. P. & Roy, S., 13 Dec 2023, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Misra, N. & Wahlstrom, M. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 29:1-29:13 13 p. 29. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 285).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  File

  • Clique 100%
  • Packing Problem 100%
  • Sparse Graphs 100%
  • Sparsity 100%
  • Positive Integer 33%
  51 Downloads (Pure)
• 2022

  A Clustering-Inspired Quality Measure for Exceptional Preferences Mining - Design Choices and Consequences.

  Verhaegh, R. F. A., Kiezebrink, J. J. E., Nusteling, F., Rio, A. W. A., Bendicsek, M. B., Duivesteijn, W. & Schouten, R. M., 2022, Discovery Science: 25th International Conference, DS 2022, Montpellier, France, October 10–12, 2022, Proceedings. Pascal, P. & Ienco, D. (eds.). Springer, p. 429-444 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13601 LNAI).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  • Quality Measure 100%
  • Field Work 100%
  • Field Research 33%
  • Normal Behavior 33%
  • Draw Conclusion 33%
  6 Downloads (Pure)

• Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel

  Bougeret, M., Jansen, B. M. P. & Sau, I., Dec 2022, In: SIAM Journal on Discrete Mathematics. 36, 4, p. 2737-2773 37 p.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

  • Polynomial 100%
  • Kernelization 100%
  • Polynomial Time 100%
  • Simple Graph 25%
  • Independence Number 25%
  3 Citations (Scopus)

  143 Downloads (Pure)

• Finding k-Secluded Trees Faster

  Donkers, H., Jansen, B. M. P. & de Kroon, J. J. H., 2022, Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers. Bekos, M. A. & Kaufmann, M. (eds.). Springer, p. 173-186 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13453 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  • Open Neighbourhood 100%
  • Tractable Algorithm 100%
  • Double Exponential 100%
  • Running Time 66%
  • Tree Problem 33%
  1 Citation (Scopus)

• Kernelization for Feedback Vertex Set via Elimination Distance to a Forest

  Dekker, D. & Jansen, B. M. P., 2022, Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Revised Selected Papers. Bekos, M. A. & Kaufmann, M. (eds.). Springer, p. 158-172 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13453 LNCS).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  Open Access

  • Polynomial 100%
  • Kernelization 100%
  • Fundamental Problem 100%
  • Graph Theory 100%
  • Open Problem 33%
  1 Citation (Scopus)

• Preprocessing for Outerplanar Vertex Deletion: An Elementary Kernel of Quartic Size

  Donkers, H., Jansen, B. M. P. (Corresponding author) & Włodarczyk, M., Nov 2022, In: Algorithmica. 84, 11, p. 3407-3458 52 p.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

  • Integer 100%
  • Edge 100%
  • Polynomial 100%
  • Finite Family 100%
  • Kernelization 100%
  2 Citations (Scopus)

  122 Downloads (Pure)

• Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies

  Jansen, B. M. P. & de Kroon, J. J. H. (Corresponding author), Jun 2022, In: Journal of Computer and System Sciences. 126, p. 59-79 21 p.

  Research output: Contribution to journal › Article › Academic › peer-review

  Open Access

  File

  • Adjacency 100%
  • Subgraphs 100%
  • Resulting Graph 100%
  • Polynomial 50%
  • Open Question 50%
  1 Citation (Scopus)

  144 Downloads (Pure)

• Search-Space Reduction via Essential Vertices

  Bumpus, B. M., Jansen, B. M. P. & de Kroon, J. J. H., 1 Sept 2022, 30th Annual European Symposium on Algorithms, ESA 2022. Chechik, S., Navarro, G., Rotenberg, E. & Herman, G. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 244).

  Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

  • Search Space 100%
  • Running Time 50%
  • Combinatorial Problem 50%
  • Transversals 50%
  • Kernelization 50%
  5 Citations (Scopus)