manuebg/thm-ptas

This repository is used for our GFSP SS23 Project

• 👋 Hi, I’m @manuEbg

thm-ptas's Issues

Unit test folder

We need a unit test folder to clean up the main function and still be able to verify that our code works.

Positions for Nodes

Use NetworkX Node Positions to position the nodes in the webview.

Export Positions to json and use them to display the graph

Cut each ring in its two-connected-components

find cut vertices and cut the ring in its two-connected-components

Depends on #21

Use reductions in configurations

There are some reductions implemented for the input graph, but they are not used in the PTAS/Exhaustive Config. Therefore they should be build in.

Parallelization

• parallelize each $k$
• parallelize each Donut
• parallelize NICE-TreeDecomposition ( quatsch )

PTAS - MIS - Implementation

struct PTASConfig {
    k : int, 
    exact_donut_tree_decomposition : bool,
    reduce_input : Vec<Reduction>,
    reduce_donuts : Vec<Reduction>,
}

enum Reduction {
    Twin,
    IsolatedClique,
    NodalFold
}

enum Scheme{
    PTAS { config : PTASConfig },
    Exhaustive { reduce_input : Vec<Reduction> }, 
}

struct MISResult {
    timings : Vec<(String, todo_TIME)>,
    total_time : todo_TIME,
    result : Vec<VertexId>,
}

fn find_max_independent_set(graph: DCEL, config: Scheme) -> Result<MISResult, Error>

fn compare_solutions(r1 : MISResult, r2 : MISResult) // print some stuff

Make each ring max. planar

Before we build the DualGraph and TreeDecompositions for each ring, we need to triangulate the ring.

Build Faces for DCEL

After reading the Planar Embedding generated in #2, we need to find the faces of the graph and fill the DCEL structure.

Adjacency Matrix

To quickly check wether a given set is independent we need an adjacency Matrix.

Find max independent set on tree decomposition

We need to find a/the maximum independent set on our tree decomposition created by #7 and #18 .

Resources:

• https://i11www.iti.kit.edu/_media/teaching/sommer2018/proseminar_nphard_problems/jenne_mwistreedecomposition.pdf
• Dynamic programming on nice tree decomposition paper
• Dynamic programming on nice tree decomposition video

Build Dualgraph

• create spanning tree #13
• create dual graph
• visualize

Generate nice tree decomposition

To be able to use dynamic programming with a tree decomposition we need to convert it into a nice tree decomposition.
See:

• Dynamic programming on Nice Tree Decompositions: https://studenttheses.uu.nl/bitstream/handle/20.500.12932/19547/thesis_lwgraaff_v2.pdf
• The Fine Details of Fast Dynamic Programming over Tree Decompositions: https://sites.cs.ucsb.edu/~daniello/papers/treewidthDpDetails.pdf

Depends on #7

Cut Graph in Donuts

Dcel::find_donuts(&self, k: usize) -> Vec<SubDcel>  ...

struct SubDcel {
   sub: Dcel,
   parent: &Dcel,
   mapping: ???
}

SubDcel :
Dcel + Mapping to ParentDcel

create data structure for planar graphs

For the project a data structure in Rust is needed to store a planar graph. Also a program is needed to read graphs from a file.

Better graph layout algorithm

Find and implement a better layout for showing our planar graphs.

Generieren von randomisierten Planaren Embeddings

Komplett in Python mit NetworkX

• Alogrithmus
• Output Format so wie hier

Proper Command Line Interface

• Some Input Args
• Some Proper Errors
• add to README.md

Compute Tree decompositions

Depends on #9

• Use an external library (for example arboretum)
• Approximate with faces (depends on #5)
  • Test result with arboretum Solver::solve()
• Evaluate results

Reduce Donuts

We need:

• a method to convert a DcelBuilder to a QuickGraph

Reduce Dual Graph for easier tree decomposition

...

Data structure for tree decomposition

We need a Data structure to store and work on tree decompositions.

Find Independent Sets in tree decomposition

Depends on #9

• Example tree decomposition
• Find max. Independent Set

BFS on DCEL

To cut the graph into multiple rings, we need an implementation of the BFS algorithm for our DCEL.
The spanning tree built by this BFS is also necessary to compute tree decompositions (#7) for each ring.

• Implement Algorithm
• Visualize Spanning trees

Implement Reduction trait for DCEL

see #8 for more information

and reduce dcel

Reduce input graph

To solve the Maximum Independent Set problem efficiently it may be useful to reduce the input graph.
In chapter 4 of this master thesis we may find further information.

General TODO-List

Implementierung des Algorithmus

1. Datenstruktur für planare Graphen (Embedding)
   • Double connected edge list
   • Reduction trait
2. Planare Graphen generieren
   • visualisieren
3. Graph in Donuts unterteilen
   • visualisieren
   • make each ring maximal planar
   • Fake-Root
4. Für jeden Donut eine Nice Baumzerlegung erstellen
   • Approximation, Heuristik oder Library für perfekte Zerlegung
   • visualisieren
5. Für jede Baumzerlegung muss das Maximum Indepentend Set gefunden werden
6. Lösungen der Independent Sets müssen miteinander kombiniert werden

Testen des Algorithmus

• Vergleich mit optimaler Lösung, Heuristiken oder anderen Approximationen
• Laufzeittests durchführen

Referenzen

• Genrieren Planarer Graphen
• Embeddings
• Doubly Connected Edge List 1
• Planar Embedding NetworkX