Steven Kelk's homepage

I am an Associate Professor at the Department of Department of Advanced Computing Sciences (formerly Data Science and Knowledge Engineering) at Maastricht University in the Netherlands, where I am the area coordinator of the Algorithms (formerly Algorithms, Complexity and Optimization (ALGOPT)) group. I am also the contact person at Maastricht for, and a board member of, the Dutch discrete mathematics cluster DIAMANT (a current list of DIAMANT members at Maastricht can be found at the start of this presentation). My contact details are here. I was vice-chair of the Maastricht Young Academy (MYA) from 2017-2019.

Outside university I am active on issues relating to public services and social justice, particularly housing and education, and I am a board member of Housing Association Soweto. I fully support the occupation of the A12 in Den Haag by Extinction Rebellion on 28th January 2023.

Maastricht students: I am also available for bachelor and masters projects, see these slides for my preferred generic research topics. More detailed topics will be announced each year via the Bachelor/Master thesis coordinators.

2018 Lorentz workshop: The Future of Phylogenetic Networks  15 – 19 October 2012 Leiden, Netherlands        Scientific organizers: Leo van Iersel (Amsterdam) Steven Kelk (Maastricht) David Morrison (Uppsala) Leen Stougie (Amsterdam) Follow-up in July 2014! Click image below:

The Dutch Day on Optimization was held on 9th November 2023 in Maastricht, see this webpage. There is a news item here and there are some photos here.

Publications/Papers

• A 2-approximation algorithm for the softwired parsimony problem on binary, tree-child phylogenetic networks, Martin Frohn and Steven Kelk, submitted 10th October 2023, to appear in Annals of Operations Research 2025. (This is a primal-dual approximation algorithm -- there are not that many in phylogenetics!)
• A branch-&-price approach to the unrooted maximum agreement forest problem, Martin Frohn, Steven Kelk and Simona Vychytilova. Submitted 5 october 2024.
• Split-or-decompose: Improved FPT branching algorithms for maximum agreement forests. David Mestel, Steven Chaplick, Steven Kelk and Ruben Meuwese. 26th September 2024.
• Reconstructing semi-directed level-1 networks using few quarnets, Martin Frohn, Niels Holtgrefe, Leo van Iersel, Mark Jones, Steven Kelk. Submitted 9th September 2024.
• Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs, Steven Chaplick, Martin Frohn, Steven Kelk, Johann Lottermoser, Matus Mihalak, submitted 15th March 2024. To appear in Discrete Applied Mathematics 2025, link.
• Invariants for level-1 phylogenetic networks under the random walk 4-state Markov model, M. Frohn, N. Holtgrefe, L. van Iersel, M. Jones, and S. Kelk, submitted 16th July 2024.
• Agreement forests of caterpillar trees: complexity, kernelization and branching. Steven Kelk and Ruben Meuwese, to appear in Theoretical Computer Science (2024).
• Deep kernelization for the Tree Bisection and Reconnnect (TBR) distance in phylogenetics. Steven Kelk, Simone Linz and Ruben Meuwese, 9th June 2022. To appear in Journal of Computer and System Sciences, 2024.
  • I gave a presentation about this work to the Algorithms group at the University of Utrecht in June 2022: Utrecht_Kelk_2022_Web_Version.pdf. It describes (only) the high-level idea behind the reduction rules.
  • An even shorter (15 minute) version of the talk was given at the "Emerging Mathematical Frontiers in Molecular Evolution" workshop at the Institut Mittag-Leffler in Sweden in August 2022. Here are the slides. There is a video of this talk here.
• Convex characters, algorithms and matchings, Steven Kelk, Ruben Meuwese and Stephan Wagner, submitted late November 2021. To appear in SIDMA, September 2023. I gave a presentation about this at the DIAMANT Autumn Symposium 2022, the slides are here. There is a PDF of the accepted version of the article here.
• Relaxed agreement forests. Virginia Aardevol Martinez, Steven Chaplick, Steven Kelk, Ruben Meuwese, Matus Mihalak, Georgios Stamoulis, pre-print 1 september 2023, to appear in SOFSEM 2024. There is accompanying code and data here. An expaned version has been submitted to Journal in early September 2024.
• Snakes and ladders: a treewidth story. Steve Chaplick, Steven Kelk, Ruben Meuwese, Matus Mihalak, Georgios Stamoulis. Pre-print released February 2023. To appear at the conference WG2023. (As a spin-off, this proves that the common chain reduction applied to two unrooted trees preserves treewidth in the display graph, resolving an open question mentioned here).
• Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance, Steven Kelk, Simone Linz, Ruben Meuwese, submitted February 21st 2022. To appear in Information Processing Letters (accepted October 2022).
• An improved kernel for the flip distance problem on simple convex polygons, Miguel Bosch Calvo and Steven Kelk, May 2022. To appear in Information Processing Letters 2023. A preliminary, shorter version (without experiments) appeared in the Canadian Conference on Computational Geometry 2021. Proceedings are here.
• New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees, Sander Borst, Leo van Iersel, Mark Jones, Steven Kelk, July 2020. Accepted January 2022: to appear in Algorithmica.
• Applicability of several rooted phylogenetic network algorithms for representing the evolutionary history of SARS-CoV-2, Rosanne Wallin, Leo van Iersel, Steven Kelk and Leen Stougie, to appear in BMC Biology and Evolution, link
• Reflections on kernelizing and computing unrooted agreement forests. Rim van Wersch, Steven Kelk, Simone Linz and Georgios Stamoulis, 14th December 2020. To appear in Annals of Operations Research 2022. There is some supporting data/code here, including the lower-bounds-via-sampling code. A copy of Tubro is available on request.
• Sharp upper and lower bounds on a restricted class of convex characters, Steven Kelk and Ruben Meuwese, submitted 22nd July 2021. To appear in Electronic Journal of Combinatorics, 2022, DOI: https://doi.org/10.37236/10589 There is a video talk here about this paper, given as part of the online seminar on algorithms and complexity in phylogenetics. The slides are here.
• A modified Integer Linear Programming formulation for the construction of classification trees, Van Dijk et al, unpublished manuscript, march 2021.
• This blog posting by Rosanne Wallin, Leo van Iersel, Mark Jones, myself and Leen Stougie summarizes the MSc work of Roseanne Wallin, in which she constructs rooted phylogenetic networks for SARS-CoV-2. November 16th 2020.
• Short opinion piece: "Phylogenetics and parameterized complexity" in the October 2020 edition of the Parameterized Complexity newsletter.
• In July 2020 I was awarded an NWO KLEIN 1 grant for 1 PhD student to work on kernelization in phylogenetics. Formal recruitment has begun, please apply here. Informal queries from (serious) candidates are welcome. The main goal of the project is to extend the work in the 'New reduction rules for the tree bisection and reconnection distance' article, below. Update 22nd December 2020: The position has now been filled.
• New reduction rules for the tree bisection and reconnection distance, Steven Kelk and Simone Linz, Annals of Combinatorics (2020), DOI
  • Here is a presentation about this work that I gave at Oxford Computer Science department in June 2019.
  • I gave a talk about this work - and empiricial experiments - at the Algorithms and Complexity in Phylogenetics (Dagstuhl Seminar 19443). The work on empirical experiments is forthcoming.
• Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm. Mark Jones, Steven Kelk and Leen Stougie, arXiv version april 2020, to appear in Journal of Computer and System Sciences.
• Cutting an alignment with Ockham's razor. Mark Jones, Philippe Gambette, Leo van Iersel, Remie Janssen, Steven Kelk, Fabio Pardi and Celine Scornavacca. Submitted, October 2019.
  • The accompanying software CUTAL is available here.
• Treewidth of display graphs: bounds, brambles and applications, Remie Janssen, Mark Jones, Steven Kelk, Georgios Stamoulis, Taoyang Wu. Journal of Graph Algorithms and Applications 23(4): 715-743 (2019)
• A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees, Steven Kelk and Simone Linz. SIAM Journal on Discrete Mathematics, 2019, Vol. 33, No. 3 : pp. 1556-1574. There is a blog posting about this article.
• A machine learning approach to algorithm selection for exact computation of treewidth. Borislav Slavchev, Evelina Masliankova, Steven Kelk, accepted september 2019. Algorithms 2019, 12(20), 200. (Part of the special issue on New Frontiers in Parameterized Complexity and Algorithms).
• Deciding the existence of a cherry-picking sequence is hard on two trees, Janosch Docker, Leo van Iersel, Steven Kelk and Simone Linz, to appear in Discrete Applied Mathematics (accepted January 2019, submitted 30th November 2017.)
• A third strike against perfect phylogeny, Leo van Iersel, Mark Jones and Steven Kelk, arXiv pre-print 19th april 2018. To appear in Systematic Biology.
• Integrality gaps for colorful matchings , Steven Kelk and Georgios Stamoulis, to appear in Discrete Optimization, december 2018 (link).
• Finding a most parsimonious or likely tree in a network with respect to an alignment. Steven Kelk, Fabio Pardi, Céline Scornavacca, Leo van Iersel, to appear in Journal of Mathematical Biology (2018).
• Discovery of important subsequences in electrocardiogram beats using the nearest neighbour algorithm , Ricards Marcinkevics, Steven Kelk, Carlo Galuzzi and Berthold Stegemann, January 2019, unpublished manuscript.
• Treewidth distance on phylogenetic trees. Steven Kelk, Georgios Stamoulis, Taoyang Wu, to appear in Theoretical Computer Science (2018), link, preprint: CoRR abs/1703.10840 (2017)
• On a fixed haplotype variant of the minimum error correction problem, Axel Goblet, Steven Kelk, Matus Mihalak and Georgios Stamoulis, submitted 9th march 2018. Proceedings of COCOON 2018, PDF
• New! ERC Consolidator grant awarded to Dr. Cameron Browne, who will join our department in mid-2018. His research, about (the history of) board games, will be embedded in both our Game AI and phylogenetics research groups. For full story see here.
• New Lorentz workshop confirmed for Summer 2018! Distinguishability in genealogical phylogenetic networks, 13-17 August 2018, Lorentz Center, Leiden. Scientific organizers: Leo van Iersel, Steven Kelk, David Morrison and Celine Scornavacca. Details follow soon.
• Improving Card Fraud Detection Through Suspicious Pattern Discovery. Fabian Braun, Olivier Caelen, Evgueni N. Smirnov, Steven Kelk, Bertrand Lebichot. IEA/AIE (2) 2017: 181-190
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems, Leo van Iersel, Steven Kelk, Georgios Stamoulis, Leen Stougie and Olivier Boes, 2nd September 2016, to appear in Algorithmica (2017)
• ToTo: An open database for computation, storage and retrieval of tree decompositions, Rim van Wersch and Steven Kelk, august 2016, Discrete Applied Mathematics 217P3 (2017) pp. 389-393. A pre-print is available here.
  • See http://treedecompositions.com/ to use ToTo.
• A note on convex characters, Fibonacci numbers and exponential-time algorithms, Steven Kelk and Georgios Stamoulis, 27th July 2016. (An earlier version of this article was released in August 2015) Advances in Applied Mathematics, Volume 84, March 2017, Pages 34-46. (DOI)
  • The accompanying software CONVEXMPDIST is available here and the software CONVEXCOUNT is available here.
• Book review of "Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing" by Makinen et al, SIGACT News 47(3):15-18 (2016).
• Do branch lengths help to locate a tree in a phylogenetic network? Philippe Gambette, Leo van Iersel, Steven Kelk, Fabio Pardi, Celine Scornavacca. Bulletin of Mathematical Biology 78(9), 1773-1795 (2016).
• Book review of "ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks" by Dan Gusfield. SIGACT News 47(1), 12-15, March 2016. (The pre-edit of the review can be read here.)
• Reduction rules for the maximum parsimony distance on phylogenetic trees, Steven Kelk, Mareike Fischer, Vincent Moulton, Taoyang Wu. Theoretical Computer Science (2016), DOI.
• A resolution of the static formulation question for the problem of computing the history bound, Julia Matsieva, Steven Kelk, Celine Scornavacca, Chris Whidden, and Dan Gusfield, to appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 2016.
• From phylogenetic trees to phylogenetic networks: possible applications outside biology - talk I gave at the Lorentz workshop Capturing phylogenetic algorithms for linguistics (Leiden, October 26th-30th 2015).
• A linear bound on the number of states in optimal convex characters for maximum parsimony distance, Olivier Boes, Mareike Fischer, Steven Kelk, 21st June 2015. To appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 2016.
• Phylogenetic incongruence through the lens of Monadic Second Order logic, Steven Kelk, Leo van Iersel, Celine Scornavacca, Mathias Weller, Journal of Graph Algorithms and Applications (JGAA) 20(2), pp. 189-215 (2016). Note that the arXiv version is somewhat different to the JGAA version.
• On the complexity of computing MP distance between binary phylogenetic trees, Steven Kelk and Mareike Fischer (December 12th 2014). Annals of Combinatorics 21(4), 573-604, 2017.
  • Accompanying software MPDIST is here.
• Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees, Leo van Iersel, Steven Kelk, Nela Lekic and Simone Linz (October 9th 2014). To appear in Theoretical Computer Science (2015), DOI
• The agreement problem for unrooted phylogenetic trees is FPT, Celine Scornavacca, Leo van Iersel, Steven Kelk, and David Bryant (June 2014), to appear in Journal of Graph Algorithms and Applications (JGAA).
• On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters, Philippe Gambette, Katharina Huber, Steven Kelk, to appear in Journal of Mathematical Biology (2016/2017).
• On low treewidth graphs and supertrees, Alexander Grigoriev, Steven Kelk and Nela Lekic, 11th february 2014. Preliminary version in AlCoB 2014. Journal version to appear in Journal of Graph Algorithms and Applications (JGAA), June 2015.
• Hybridization Number on Three Rooted Binary Trees is EPT. Leo van Iersel, Steven Kelk, Nela Lekic, Chris Whidden and Norbert Zeh. To appear in SIAM Journal on Discrete Mathematics (SIDMA) 2016. (Earlier title was Hybridization Number on Three Trees).
• On the Maximum Parsimony distance between phylogenetic trees, Mareike Fischer and Steven Kelk, Annals of Combinatorics 20(1), pp 87-113 (2016).
• A short note on exponential-time algorithms for hybridization number, Leo van Iersel, Steven Kelk, Nela Lekic, Leen Stougie, 4 december 2013.
• A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees, Leo van Iersel, Nela Lekic, Steven Kelk, Celine Scornavacca, November 2013, BMC Bioinformatics (2014).
  • This is the journal version of the WABI 2012 paper. We have extended it to nonbinary trees.
• Kernelizations for the hybridization number problem on multiple nonbinary trees, Leo van Iersel and Steven Kelk, 16th November 2013. To appear in Journal of Computer and System Sciences (JCSS), 2016. Conference version in WG 2014. See also the TREEDUCE software below.
• Fighting network space: it is time for an SQL-type language to filter phylogenetic networks, Steven Kelk, Simone Linz, and David A. Morrison, October 2013 (unpublished opinion piece, arXiv).
• Exact reconciliation of undated trees. Leo van Iersel, Celine Scornavacca and Steven Kelk, september 2013 (arXiv manuscript).
  • See the accompanying software ILPEACE.
• Ancient dispersal of the human fungal pathogen Cryptococcus gattii from the Amazon rainforest, Hagen et. al., PLOS ONE, June 2013. (Link to press release).
• Recent advances in rooted phylogenetic networks: the long road to explicit hypothesis generation. Talk at conference Mathematical and Computational Evolutionary Biology (MCEB 2013), May 2013.
• Bapteste, E., van Iersel, L. Janke, A., Kelchner, S., Kelk, S., McInerney, J.O., Morrison, D.A., Nakhleh, L., Steel, M., Stougie, L. and Whitfield, J. (2013). Networks: Expanding evolutionary thinking. Trends in Genetics (in press).
• On Computing The Maximum Parsimony Score Of A Phylogenetic Network, Mareike Fischer, Leo van Iersel, Steven Kelk, Celine Scornavacca, arxiv (11 feb 2013). To appear in SIDMA (2015).
  • See also the accompanying software MPNet.
• Approximation algorithms for nonbinary agreement forests, to appear in SIDMA (2014). This extends the article 'Computing nonbinary agreement forests' by including results for MAAF (and not just MAF).
• Computing nonbinary agreement forests, Leo van Iersel, Steven Kelk, Nela Lekic and Leen Stougie, arXiv (2012)
  • See also the MAF software on Leo's webpage.
• What mathematical optimization can, and cannot do, for biologists - presentation at the Lorentz workshop on the Future of Phylogenetic Networks (October 2012).
• Optimal flux spaces of genome-scale stoichiometric models are determined by a few subnetworks, Steven Kelk, Brett Olivier, Leen Stougie, Frank Bruggeman, Nature Scientific Reports 2, 580; DOI:10.1038/srep00580 (2012)
• Towards the fixed parameter tractability of constructing minimal phylogenetic networks from arbitrary sets of nonbinary trees, Steven Kelk and Celine Scornavacca, 30th July 2012. Submitted.
• A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees, Teresa Piovesan and Steven Kelk, July 25th 2012. To appear in IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB).
  • There is an experimental implementation of this algorithm here: TERMINUSEST. Update 9th September 2013: I have just released Version 2 of TerminusEst, which is much faster than the original version when hashing is switched on.
• A practical approximation algorithm for solving massive instances of hybridization number, Leo van Iersel, Steven Kelk, Nela Lekic and Celine Scornavacca, may 2012. To appear in WABI 2012. The program CycleKiller can be downloaded here.
• Cycle killer...qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set, Steven Kelk, Leo van Iersel, Nela Lekic, Simone Linz, Celine Scornavacca, Leen Stougie, december 22nd 2011. To appear in SIAM Journal on Discrete Mathematics (SIDMA).
• A note on efficient computation of hybridization number via softwired clusters, Steven Kelk, august 2011.
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Steven Kelk and Celine Scornavacca, august 2011. To appear in Algorithmica, link.
• Book review: Phylogenetic Networks: Concepts, Algorithms and Applications, Steven Kelk, Systematic Biology 2011; doi: 10.1093/sysbio/syr054
• Algorithmic aspects of phylogenetic network construction - these are slides (in PDF) from a talk I gave in April 2011 at the IPA Lentedagen in the Netherlands.
• On the elusiveness of clusters, Steven Kelk and Celine Scornavacca and Leo van Iersel, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 9(2) (March-April 2012), pp. 517-534.
• When two trees go to war, Leo van Iersel and Steven Kelk, Journal of Theoretical Biology 269 (2011), pp. 245-255.
• A short note on the tractability of constructing phylogenetic networks from clusters, Leo van Iersel and Steven Kelk, arXiv pre-print 22 december 2009.
• A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks, Katharina T. Huber, Leo van Iersel, Steven Kelk, Radoslaw Suchecki, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 8(3) (May-June 2011), pp. 635-649.
• LEV1ATHAN, the algorithm from the above paper, is available for download from this website.
• Phylogenetic Networks Do not Need to Be Complex: Using Fewer Reticulations to Represent Conflicting Clusters, Leo van Iersel, Steven Kelk, Regula Rupp, Daniel Huson, arXiv pre-print 16 october 2009. March 2010: Accepted to ISMB2010, thereafter to appear in Bioinformatics 2010 26(12):i124-i131.
  • CASS, the algorithm from the above paper, has now been incorporated into Dendroscope. CASS also has its own website, see here.
• Some mathematical refinements concerning error minimization in the genetic code, Harry Buhrman, Peter T. S. van der Gulik, Steven M. Kelk, Wouter M. Koolen, Leen Stougie, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 8(5) (Sept-Oct 2011) pp. 1358-1372.
• An early release of SIMPLISTIC (SIMPLe network heurISTIC) is now available! SIMPLISTIC is a program, written in Java, which always returns some network consistent with 100% of the dense input triplets. See this page for code and documentation (28 july 2008). There is a poster here about SIMPLISTIC (and MARLON.)
• Constructing the Simplest Possible Phylogenetic Network from Triplets, Leo van Iersel and Steven Kelk, Algorithmica, 60, pp. 207-235 (2011). (Available on-line)
  • MARLON (Minimum Amount of Reticulation Level One Network) can be downloaded here.
  • A version of the paper has been accepted to appear in ISAAC2008.
• Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks, Leo van Iersel, Steven Kelk, Matthias Mnich, Journal of Bioinformatics and Computational Biology (JBCB) 7(4):597-623 (2009)
• Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks, Jaroslaw Byrka, Pawel Gawrychowski, Katharina T. Huber, Journal of Discrete Algorithms 8(1):65-75 (2010)
• In February 2008 we produced a new version of the paper, with a heavily optimized running time for the derandomization, and a very fast triplet consistency checking algorithm as subroutine.
• Slides from a presentation about this article, given at both Technische Universiteit Eindhoven and the Isaac Newton Institute (Cambridge, England).
• Constructing level-2 phylogenetic networks from triplets, Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, Ferry Hagen, Teun Boekhout, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(4):667-681 (2009).
  • Powerpoint slides used in presentations at University of East Anglia and University of Liverpool, summer 2007.
  • September 2007: Here is a practical implementation of the algorithm in Java: LEVEL2
  • December 2007: The article has been accepted to appear in RECOMB2008.
• Shorelines of islands of tractability: Algorithms for parsimony and perfect phylogeny haplotyping problems, Leo van Iersel, Judith Keijsper, Steven Kelk and Leen Stougie, IEEE/ACM Transactions on Computational Biology and Bioinformatics April-June 2008 (Vol. 5, No. 2) pp. 301-312. This is the journal version of the WABI paper Beaches... and contains new approximation results for PH and MPPH not found in the WABI version. The essence of the approximation results is explained in this presentation given at Bielefeld University (Germany) in November 2006.
• Beaches of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems, Leo van Iersel, Judith Keijsper, Steven Kelk and Leen Stougie. A conference version was presented at WABI2006. (WABI slides are available here.)
• Prefix reversals on binary and ternary strings, Cor Hurkens, Leo van Iersel, Judith Keijsper, Steven Kelk, Leen Stougie, John Tromp, SIAM Journal on Discrete Mathematics, 21(3), pp. 592--611 (2007).
  • There is a poster here about this paper.
  • Conference version appears in Algebraic Biology 2007, LNCS4545 pp. 292--307, DOI 10.1007/978-3-540-73433-8_21
• On the complexity of the Single Individual SNP Haplotyping Problem, Rudi Cilibrasi, Leo van Iersel, Steven Kelk and John Tromp, Algorithmica 49(1), pp. 13-36 (2007), DOI 10.1007/s00453-007-0029-z
• On the complexity of several haplotyping problems, Rudi Cilibrasi, Leo van Iersel, Steven Kelk and John Tromp, Algorithms in Bioinformatics: 5th International Workshop, WABI 2005, Mallorca, Spain, October 3-6, 2005, LNCS 3692 / 2005, pp. 128-139.
• On the relative complexity of approximately counting H-colourings, Steven Kelk, PhD Thesis, University of Warwick, 2004. (3.5mb, PDF)
• The complexity of choosing an H-colouring (nearly) uniformly at random, L.A. Goldberg, S. Kelk and M. Paterson, SICOMP, 33(2) 416-432 (2004) copyright SIAM (preliminary version STOC 2002)

Links to pages of some regular co-authors

• Leo van Iersel
• Celine Scornavacca
• Simone Linz

Links to books (etc.) about phylogenetic networks

• Phylogenetic Networks by Daniel H. Huson, Regula Rupp and Celine Scornavacca, 2010
• Introduction to Phylogenetic Networks by David Morrison, 2011
• The Genealogical World of Phylogenetic Networks -- Blog by David Morrison, Leo van Iersel and myself (launched feb 2012)

Software for phylogenetic networks (and trees) - and related topics

• MRAF - A simple combination of Java and MiniZinc for computing a Maximum Relaxed Agreement FOrest (MRAF) of two unrooted binary trees.
• Tubro - aggressive kernelization for TBR distance. See this article. (Available on request).
• ConvexBound - generates via sampling strong lower bounds on dMP and dTBR.
• CUTAL - optimally partitions an alignment into blocks, using parsimony as the guiding principle. (Main developer is Mark Jones).
• CONVEXCOUNT - counts or samples convex characters on a given unrooted binary tree
• CONVEXMPDIST (does not use ILP) - computes maximum parsimony distance exactly
• MPDIST (uses ILP) - computes maximum parsimony distance exactly
• TREEDUCE - kernelizes arbitrary sets of rooted nonbinary trees in polynomial time
• Nonbinary CycleKiller - approximates hybridization number on two nonbinary rooted trees by optimally breaking cycles in an induced graph
• ILPEACE - computes optimal reconciliation of two trees, using ILP
• MPNet - computes parsimony score of a phylogenetic network, uses ILP
• MAF - computes maximum agreement forest on nonbinary trees
• TerminusEst - FPT algorithm that computes hybridization number exactly on two rooted nonbinary trees. Much faster than you would expect :)
• CycleKiller - approximates hybridization number on two binary rooted trees by optimally inducing cycles in an induced graph
• CASS - computes a phylogenetic network of low level (i.e. few reticulations per biconnected component) from a set of softwired clusters
• LEV1ATHAN - computes a level-1 network that displays as many of the given input triplets as possible
• SIMPLISTIC - constructs level-k networks from dense sets of input triplets
• MARLON - constructs level-1 networks with a minimum number of reticulations, from a dense set of input triplets
• LEVEL2 - constructs a level-2 network consistent with a given set of input triplets

Miscellaneous scientific links

• My Mastodon page
• DIAMANT - Discrete, Interactive and Algorithmic Mathematics, Algebra and Number Theory
• I'm only happy when it rains - why negative results in computer science should be celebrated, not feared! Somewhat tongue-in-cheek presentation I gave to our student assocation (Incognito) a couple of years back. Still relevant today (august 2018), so I thought I'd upload it. I can't remember where all the images came from - if I have used your image but not referenced you, please let me know - I will be happy to add a reference. The translation into Yoda-speak was courtesy of The Yoda-Speak Generator.
• Dutch Network on the Mathematics of Operations Research (LNMB)
• Dutch Seminar on Optimization (on-line) - excellent initiative that started during Covid-19
• Dutch Combinatorics Network (DCN)
• Theoretical Computer Science Stack Exchange - a huge range of research-level questions and answers about TCS
• Operations Research Stack Exchage - excellent stack exchange for more practical computation (ILP questions, lots of solvers etc.)
• David Eppstein's blog (graph theory, computational complexity and suchlike)
• Godel's lost letter and P=NP blog by Dick Lipton and Ken Regan.
• Computational complexity blog by Lance Fortnow and Bill Gasarch.

Miscellaneous publications

• De jacht op huurders gaat door, September 2012. Article (in Dutch) about the plans of the Dutch state to further liberalise and privatise the Dutch rental housing stock.
• A (very) rough guide to Amsterdam housing policy, Carla Huisman and Steven Kelk, 2008. As its name suggests, it's very rough... it could originally be found at housingamsterdam.org/po\_inside/roughguide2008.doc
• Trading It Away - How GATS Threatens UK Higher Education, Steven Kelk and Jess Worth, October 2002. This report disappeared from the internet several years ago and after much searching I succeeded in finding and uploading a PDF version of it.
• A flawed argument, 14 november 2002. Guardian article I wrote about GATS.

Miscellaneous political links

• We need to act - statement by various Maastricht groups on the occasion of the national education strike, 15th March 2019.
• Red Pepper magazine
• Momentum
• Algemene Onderwijsbond - this Dutch education union now has a wing for universities.
• Woningbouwvereniging Soweto
• Education International
• Public Services International
• Scientists4Future (NL) - coalition of scientists concerned about climate change
• Extinction Rebellion (NL)

Random stuff

• The Social Life of Small Urban Spaces (301mb, 58minutes) - this fascinating and highly influential video (William H. Whyte) is very hard to find on the internet in this full version, so I decided to mirror it.
• Uncut magazine - excellent monthly music magazine, already worth the price for the CD they distribute with it every month.
• Book of The New Sun by Gene Wolfe - my favourite book. It is actually a tetrology, or a pentalogy if you include the coda The Urth of the New Sun.
• Rush Hour by Jane Wiedlin - possibly the best pop song ever?
• My favourite band: VNV Nation (no, they don't sound like Jane Wiedlin). Other bands I like very much: Depeche Mode, New Order, REM, Idlewild, Chvrches, Lord Huron, Drive by Truckers. I keep a YouTube playlist of alt-country, americana and stuff like that here.
• I'm a huge fan of Cricket and also enjoy playing it when the opportunity arises (I guess I would describe myself as a medium-pace right-arm seam bowler who gets up to medium-fast if I'm not too stiff...) If you have no idea what Cricket is, the description of the game on Wikipedia is long but comprehensive. This five minute video does a pretty good of explaining the basic rules. I had the pleasure of being at Headingley on Day 4 of the third Ashes test, August 25th 2019...short highlights are here. A day to never forget.
• Guerilla Cricket
• Maastricht Cricket Club

Last updated: 17th December 2024.