We are always looking for enthusiastic young people who are interested in a research project or thesis in the Bachelor, Master, and PhD programs. There are often topics available that are not listed here, so please contact us if you are interested in a project or thesis within an area of our group's research.
Contents
Solving Hard Combinatorial Problems with SAT and QBF Solvers
Over the last two decades, SAT-solvers (which are programs that solve the Boolean satisfiability problem) have become surprisingly powerful and can check the satisfiability of instances with hundreds of thousands of variables in a few minutes. Among the most powerful SAT-solvers are Glucose and Lingeling.The subject for a Bachelor or Masters thesis would be to translate a hard combinatorial problem into SAT and solve it with a SAT-solver. For such a translation (often called encoding) there are usually many different approaches, and part of the thesis would be to compare different approaches experimentally on a set of problem instances.
The considered combinatorial problem can be chosen from a large pool of problems, including graph, clustering and optimization problems. Some recent research in this direction can be found here and here.
For even harder problems, like finding a winning strategy for a board game, one needs to go beyond SAT and use a QBF solver (Qute is such a solver we developed in our group).
Date: February 2018
Topic for: Bachelor/Master Theses
Contact: Stefan Szeider
Solving the Repetition-Free Longest Common Subsequence Problem by an A* Algorithm
Date: 30.01.2018
Topic for: Master Thesis
Contact: Marko Djukanovic or Günther Raidl
In the last decade combinatorial optimization problems on strings appear frequently in many applications like pattern recognition, data compression and in particular biology and genetics. We consider the Repetition-Free Longest Common Subsequence (RFLCS) problem which is stated as follows. A subsequence of a string is obtained by removing any letters of an input string. The longest common subsequence (LCS) of a set of input strings is a string that is a subsequence of all input strings and has maximum length. The RFLCS seeks a longest common subsequence of its input strings with the additional property that each letter appears only at most once.
For example: Given two strings s1="ATGCTGHAAB" and s2="AAABTGGABBE", the solution of the RFLCS is the string s="ATGB".
The RFLCS is known to be NP-hard, more precisely it is even APX-hard for only two input strings. In this project, an A-based algorithm shall be developed and compared to existing methods in the literature. The intended A algorithm can be built upon a recently developed framework addressing other LCS problem variants.
Finding Planarizing Perfect Pseudo Matchings in Snarks
Date: 24.11.2017
Topic for: Master Thesis
Contact: Benedikt Klocker or Günther Raidl
One of the most famous open conjectures in graph theory is the cycle double cover conjecture. It simply asks if there exists for every bridgless graph a set of cycles that cover every edge of the graph exactly twice. If we can find for a graph a planarizing perfect pseudo matching, then the graph has a cycle double cover. Therefore, the problem of finding planarizing perfect pseudo matchings is strongly related to the cycle double cover conjecture.
A pseudo matching of a graph is a subgraph whose connected components are either K2s (only one edge) or claws (a vertex connected to 3 other vertices). A pseudo matching is perfect if it contains all vertices of the graph. A pseudo matching is planarizing if the graph after contracting all connected components of the pseudo matching is planar.
It is shown that the cycle double cover conjecture is true if and only if it is true for the class of all snarks, a special class of graphs, which is well studied in literature. Therefore, it is especially interesting for us to find planarizing perfect pseudo matchings in the class of all snarks. As snarks are very well studied and there are effective techniques to generate all snarks up to a certain size we can use this techniques to generate a large number of test instances for our problem.
We are looking for a motivated master student who wants to work on this subject within the scope of her/his master thesis. The goal would be to develop an algorithm for finding planarizing perfect pseudo matchings using exact techniques like branch-and-bound, mixed integer linear programming, constraint programming, ... or heuristic approaches like VNS, GRASP, EA, ACO, ...
Needed skills:
- Basic knowledge in exact and/or (meta-)heuristic optimization methods (e.g., from Heuristic Optimization Techniques, Algorithmics)
- Interest in graph theory and optimization
- Programming skills
Graph Drawing
Date: September 2017
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg
Graph Drawing is concerned with algorithms to compute geometric representations of graphs and networks. Applications of graph drawing range from graph visualizations for human users to hardware layouts and wireless routing. Scientifically, the area offers a wide spectrum of topics for student theses, from theoretical questions (e.g., existence of certain layouts or algorithms with certain properties) to practical questions of modeling the actual requirements of a particular application and designing, implementing, and evaluating algorithms for solving it.
Requirements:
- Proficiency in (graph) algorithmics
- Interest in geometry and visualization
- Practical topics: good programming skills
Algorithmic Cartography and Geometry
Date: September 2017
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg
Digital cartography offers a wide spectrum of visualization problems that can be solved by geometric algorithms. The types of maps range from dynamic and interactive maps, e.g., on smart phones and mobile devices, to unconventional diagrammatic or schematic maps. Examples of algorithmic problems comprise label placement for map features, algorithms for constructing cartograms, or schematic destination maps. The area contains both topics with a stronger practical focus (including evaluation) or with a more theoretical focus. Thesis topics in computational geometry without direct links to cartography are also possible.
Requirements:
- Proficiency in algorithmics and geometric algorithms
- Interest in maps and interdisciplinary work
- Practical topics: good programming skills
