User Tools

Site Tools


2ima00

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
2ima00 [2016/05/26 12:12]
bmpjansen [Student lectures]
2ima00 [2016/05/26 12:27] (current)
bmpjansen [Student lectures]
Line 143: Line 143:
  
 **Treewidth:​ Henk & Xi.** **Treewidth:​ Henk & Xi.**
 +
 +There are 2 approaches for solving the problem when you have a tree decomposition. The first one has a running time of 3^k * poly(n), harder to understand, but may be easier to implement:
  
 [[https://​arxiv.org/​pdf/​1103.0534v1.pdf|Cygan et al.: Solving connectivity problems parameterized by treewidth in single exponential time]] [[https://​arxiv.org/​pdf/​1103.0534v1.pdf|Cygan et al.: Solving connectivity problems parameterized by treewidth in single exponential time]]
 +
 +The next approach has a worse factor f(k), but a better polynomial term (linear), and is conceptually simpler:
 +
 [[http://​link.springer.com/​chapter/​10.1007%2F3-540-36379-3_25|Ton Kloks, C.M. Lee, Jiping Liu. New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs]] (page 8 and further) [[http://​link.springer.com/​chapter/​10.1007%2F3-540-36379-3_25|Ton Kloks, C.M. Lee, Jiping Liu. New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs]] (page 8 and further)
 +
 +I don't know which of the 2 approaches will be faster on the inputs we have; one has a worse polynomial term, the other has a worse factor f(k). I don't think it is feasible to implement both, given the time. Pick one of the two and go for it. To **find** a tree decomposition,​ you can use one of the heuristics described in this paper:
 +
 +[[http://​dx.doi.org/​10.1016/​j.ic.2009.03.008|Hans L. Bodlaender, Arie M. C. A. Koster:
 +Treewidth computations I. Upper bounds. Inf. Comput. 208(3): 259-275 (2010)]]
 +
 +Within the framework of iterative compression and you have *some* feedback vertex set X in your graph G, you can also make a tree decomposition by making a tree decomposition for the forest G - X (which is easy) and then adding all vertices of X to all bags. Afterwards, you can try to make it better by removing vertices from X from bags when the tree decomposition remains valid after removing a vertex from a bag.
  
 **Parameterized by solution size (iterative compression & randomized):​ Huib & Stefan.** **Parameterized by solution size (iterative compression & randomized):​ Huib & Stefan.**
 +
 +For the iterative compression algorithm, I think the book gives sufficient details to build an implementation from. There is a theoretically faster algorithm, which is linked below. You could read it for inspiration,​ but it's not necessary and I do not think it is feasible to implement it fully because it needs a subroutine with matroid computations.
  
 [[http://​dx.doi.org/​10.1016/​j.ipl.2014.05.001|Tomasz Kociumaka, Marcin Pilipczuk: [[http://​dx.doi.org/​10.1016/​j.ipl.2014.05.001|Tomasz Kociumaka, Marcin Pilipczuk:
 Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10): 556-560 (2014)]] Faster deterministic Feedback Vertex Set. Inf. Process. Lett. 114(10): 556-560 (2014)]]
 +
 +For the randomized algorithm, I don't know of any additional literature. You could search by yourself.
2ima00.1464257554.txt.gz ยท Last modified: 2016/05/26 12:12 by bmpjansen