To path indicator Subpages of “Teaching“ To navigation To quick access To footer with other services
To content
Algorithm Engineering
Fakultät für Informatik
Students in summer on north campus, red gears in background. © Roland Baege​/​TU Dortmund

Bachelor's theses: Dominating Set and Independent Set on graph classes

We are offering 20 Bachelor's theses in Algorithm Engineering. Every thesis addresses one of two problems – Minimum Dominating Set or Maximum Independent Set – on one particular graph class. You will research suitable algorithms, implement several of them, generate your own test instances, compare the algorithms systematically, and develop a solver tailored to your graph class.

Topic assignment will be discussed at the kick-off meeting on 1 October 2026 and will then take place via Moodle.

Prerequisites

Under the Bachelor examination regulations (BPO), registering a Bachelor's thesis requires at least 120 credit points. In addition, we require that the compulsory modules of the first semesters have been passed: DAP 1/2, RS, GTI or TIfAI, as well as the mathematics modules MafI 1/2 or HM 1–3. Please provide proof of this, for example a current transcript of records, no later than when you register the thesis.

On the technical side, we expect confident use of a programming language of your choice and a basic background in algorithms and complexity. No prior knowledge of the specific graph class is required.

The thesis may be written in German or in English. The choice of language has no bearing on the grade.

Dates

All joint meetings take place in OH14/R202 and attendance is mandatory. On the talk dates, attendance is required for the entire session, including the talks given by the other participants.

  • Thu, 1 October 2026, 10:30 – Kick-off meeting. Introduction to both problems and the 20 topics, schedule and requirements. Topic assignment will be discussed here and will then take place via Moodle.
  • by Thu, 15 October 2026 – Registration deadline. The thesis must be registered by this date. Without timely registration, participation is not possible.
  • Thu, 12 and Thu, 19 November 2026, from 9:15 – Introductory talks (10 minutes per person): definition of your graph class and presentation of the algorithms you have selected.
  • Mon, 14 to Fri, 18 December 2026 – Individual meetings (20 minutes, scheduled individually): discussion of your experimental results and what follows from them for your own solver.
  • Thu, 21 January 2027 – Q&A session. Open office hour on writing up the thesis.
  • Thu, 18 and Thu, 25 February 2027 – Final talks.

Topics

Eight of the graph classes are covered with both problems. The two students working on the same class may develop definitions and instance generators together; their results do not depend on each other.

Cluster A – Structural sparsity and decompositions

  1. Minimum Dominating Set on planar graphs
  2. Minimum Dominating Set on graphs of bounded treewidth
  3. Minimum Dominating Set on interval and chordal graphs
  4. Minimum Dominating Set on d-degenerate and bounded-degree graphs
  5. Maximum Independent Set on planar graphs
  6. Maximum Independent Set on graphs of bounded treewidth
  7. Maximum Independent Set on d-degenerate and bounded-degree graphs
  8. Maximum Independent Set on interval, chordal and permutation graphs

Cluster B – Geometric graphs

  1. Minimum Dominating Set on disk graphs: from the unit case to arbitrary radii
  2. Minimum Dominating Set on grid and polyomino graphs
  3. Minimum Dominating Set on Delaunay graphs and the proximity hierarchy
  4. Maximum Independent Set on disk graphs: from the unit case to arbitrary radii
  5. Maximum Independent Set on rectangle and square intersection graphs
  6. Maximum Independent Set on grid and polyomino graphs

Cluster C – Random models

  1. Minimum Dominating Set on hyperbolic random graphs
  2. Minimum Dominating Set on power-law graphs (Chung–Lu, preferential attachment)
  3. Minimum Dominating Set on random intersection graphs
  4. Maximum Independent Set on Erdős–Rényi graphs
  5. Maximum Independent Set on hyperbolic random graphs
  6. Maximum Independent Set on random intersection graphs

If you have any questions, feel free to contact us in advance and come to the kick-off meeting.