Mirror-friendly Minimum Spanning Tree (MFMST) Programming Contest

In addition to the project assignment of the course Computationally Hard Problems (02249), Fall 2017, we offer a programming contest for finding MFMST solutions.

Participation in the contest is not mandatory.

Background

Recently, there has been leak by the Danish Security and Intelligence Service (DSIS), revealing that several major Danish cities have been undermined by a mysterious tunnel system. The leaked documents state that workers discovered the tunnels during the ongoing building projects on the DTU campus. Rektor Anders Overgaard Bjarklev was approached by DSIS to keep matters confidential and has been asked to investigate the findings. Over the past months a team of DTU specialists has been investigating the tunnel system (cleverly disguised as the DTU Transform team). The DTU specialists try to keep matters under control and most information is classified and given out on a need-to-know-basis. The true nature of the tunnels is still a mystery. We only know that the tunnel system bears an uncanny resemblance to the street network wherever it appears. Furthermore, the tunnels seem to be highly dangerous and Bjarklev is quoted in the leaked document “It is imperative to stop the tunnels by all means necessary”. Autonomous drones are being used to track the tunnel systems.

On November 6, the DTU researchers have found a way to destroy the tunnel systems which involves radio signals. The tunnel system seems to be alive and responds to certain radio frequencies. By placing transmitters at each tunnel end and each intersection, the transmitters can irradiate the tunnels to destroy it. One big problem is that all transmitters have to send at the same frequency without any phase shift. This is usually not a problem, but radio wave propagation in the tunnels is inexplicably constricted and the frequency is too high to sync the transmitters beforehand: even the slightest phase shift renders the attempt infeasible. It is however possible to connect the transmitters using specially shielded cables in order to sync the frequencies. These cables have to be laid underground to prevent causing public sensation. Unfortunately these cables are extremely expensive and have to be used in an economical fashion since more and more cities are being affected.

There is one problem: the drones that are being used to map the tunnel systems are somehow tainted by the tunnels themselves and randomly reverse the junction and tunnel end point lists. Whenever the DTU researchers retrieve the list of intersections and tunnel end points from the drones, there is only a 50% chance that they are in the correct order. In order to use the precious cables wisely, Associate Professor Carsten Witt has been commissioned and authorised to come up with a system to overcome this problem. He quickly came up with the solution to simply prepare for both cases, i.e. the case that the list is in order and the list that it is in its reverse order. A spanning tree minimizing the cable length for both cases then yields a good estimate for the total cable length needed.

This is where you come in: due to the recent news of subterranean tunnels being found all over the world, this problem became a computational one and we are in desperate need of algorithmic solutions. You are hereby asked to help.

Gud Bevare Danmark.

Description

Consider the following decision problem:

The contest is not about the decision, but about optimization.

However, instead of answering the optimization version of the above stated decision problem exactly, we are interested in finding solutions fast, i.e. the solutions do not need to be optimal (here: minimal) as opposed to the project assignment.

Feel free to use any algorithmic tricks you want, be creative!

Programming Languages

The programs should be implemented in C, C++, Java or Python. Other languages are possible, but should be discussed with me beforehand (you may use the same language as in the project assignment if we have already talked about it). You are allowed to make use of (free) software libraries if that helps you (GSL, Boost etc).

Format

The instances are given in the same UWG format that was presented in the project assignment, e.g. an instance file can look like:

3
3
1 2 1
2 3 2
1 3 3

The built program should take an UWG file as input from the command line, i.e. if testfile.uwg is an instance file and the executable is called myprogram, your program should be invoked as ./myprogram testfile.uwg.

Solutions are encoded as a comma separated list of operations in the following way: “B, e1, …, en − 1”, more precisely

5, (3, 4), (1, 8)

In this case, 5 refers to the minimum weight of the two MSTs defined by the edges {3, 4}, {1, 8}. Whitespaces are irrelevant, as is the order of the edges, i.e. the following output is equivalent:

5,(8,1), ( 3 , 4 )

The program should then output solutions to standard output (stdout) and not to a file. If your program outputs more than one solution, the new solution should appear on a new line. In this case, the last solution counts.

Hint: simply output every improvement you find.

Submission

Every student of the course can participate in the contest. You are allowed to work in groups of up to four people, but every participant may only be part of one group.

Every entry to the contest should include the following:

  1. your team name (be creative!)
  2. a list of group members, including email addresses
  3. the source code
  4. any build instructions, for example: If your program is written in C, provide a Makefile. If your program is written in Java, provide an Ant build file.
  5. a list of library dependencies (if any), including version numbers

The entries should be packaged in a gzipped tar archive or zip file. Please don’t create tarbombs.

The submission deadline is 2017, submissions are to be sent to cgie@dtu.dk.

I will send you an email if I have received your submission, in case something gets lost in the DTU spam filter.

Scoring

Your programs will have a wall-clock time limit and will be killed after that time. Hence the possibility to output more than one solution. The maximum timeframe is 60s. The score will be based on the quality of your solutions.

Notes