2ima00

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

Both sides previous revision Previous revision Next revision | Previous revision | ||

2ima00 [2016/05/10 15:21] bmpjansen [Prequisites] |
2ima00 [2016/05/26 12:27] bmpjansen [Student lectures] |
||
---|---|---|---|

Line 119: | Line 119: | ||

| 8 | Using linear programming in parameterized algorithms | Cygan et al. 2.5 & 3.4 | ? | | | 8 | Using linear programming in parameterized algorithms | Cygan et al. 2.5 & 3.4 | ? | | ||

| 9 | Important separators | Cygan et al. 8.1-8.3 | ? | | | 9 | Important separators | Cygan et al. 8.1-8.3 | ? | | ||

+ | |||

+ | === Programming pairs for implementation === | ||

+ | The literature linked to below can be accessed when logged into the TU/e network, either through VPN or by physically being present at TU/e. | ||

+ | |||

+ | **Kernels: Chris & Leo.** | ||

+ | |||

+ | The following paper gives a kernel that is not as small, but is easier to compute, than the one given in the book. In particular, read Section 4 of this paper: | ||

+ | |||

+ | [[http://dx.doi.org/10.1007/s00224-009-9234-2| | ||

+ | Hans L. Bodlaender, Thomas C. van Dijk: | ||

+ | A Cubic Kernel for Feedback Vertex Set and Loop Cutset. Theory Comput. Syst. 46(3): 566-597 (2010)]] | ||

+ | |||

+ | Instead of requiring an algorithm to find maximum matchings, it just needs an approximation algorithm for (weighted) feedback vertex set. It was developed independently by 2 sets of authors. Pick the one you find the easiest to read: | ||

+ | |||

+ | Option 1: | ||

+ | |||

+ | [[http://dx.doi.org/10.1137/S0895480196305124|Vineet Bafna, Piotr Berman, Toshihiro Fujito: | ||

+ | A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem. SIAM J. Discrete Math. 12(3): 289-297 (1999)]] | ||

+ | |||

+ | Option 2: | ||

+ | |||

+ | [[https://dx.doi.org/10.1016%2F0004-3702%2895%2900004-6|Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.", Artificial Intelligence 83 (1): 167–188]] | ||

+ | |||

+ | **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]] | ||

+ | |||

+ | 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) | ||

+ | |||

+ | 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.** | ||

+ | |||

+ | 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: | ||

+ | 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.txt · Last modified: 2016/05/26 12:27 by bmpjansen