# Algorithms seminar series

Seminaret bygger på INF234, og er åpent for alle. I seminaret diskuteres aktuelle tema og siste nytt innen algoritmeforskning. Algoritmegruppens medlemmer presenterer jevnlig sitt arbeid. Dette er et forum der alle som er interessert i algoritmer og kompleksitet kan holde seg oppdatert.

## 2014

**Vårsemesteret 2014**

The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every **Friday**. We start with lunch at 12.00, and the seminar starts at **12.45**, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.

In charge of the seminars is Markus Dregi. Any question can be directed to markusdregi@gmail.com.

16. May | TBA | |

9. May | TBA | |

2. May | TBA | |

25. April | TBA | |

18. April | Easter | |

11. April | Marcin Pilipczuk | Online and dynamic algorithms for the Steiner tree problem. |

4. April | M S Ramanujan | Parameterized Algorithms to Preserve Connectivity. |

28. March | Sadia Sharmin | Graph Partitioning |

21. March | Winter school | |

14. March | Computing Treedepth | |

7. March | Erik Jan van Leeuwen | Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs |

28. February | Pål Grønås Drange | Subexponential Parameterized Complexity of Completion Problems |

21. February | Real algebraic geometry in computational game theory - a consumer's perspective | |

14. February | Sigve H Sæther | Domination Set parameterised by Clique-width |

7. February | Reza Saei | Finding Disjoint Paths in Split Graphs |

31. January | The r-simple k-path problem | |

24. January | Pinar Heggernes | Enumeration in Graph Classes |

17. January | Michał Pilipczuk | Minimum Bisection is FPT |

10. January | Manu Basavaraju | Partially Polynomial Kernels for SetCover and TestCover |

## 2013

**Høstsemesteret 2013**

Reza Saei was in charge of the seminars for this semester.

**Vårsemesteret 2013**

Thanks to Sigve Hortemo Sæther, for being in charge of the seminars for Spring semester.

14 June | Michał Pilipczuk | A polynomial kernel for Planar Steiner Tree parameterized by the size of the tree |

7 June | Dániel Marx | CSPs and fixed-parameter tractability |

31 May | Fredrik Manne | Efficient Sequential and Multicore Weighted Matching Algorithms |

24 May | Ondřej Suchý | On Explaining Integer Vectors by Few Homogenous Segments |

17 May | Norwegian Constitution Day | |

10 May | Mamadou Kanté | On the linear rank-width and linear clique-width of Trees |

3 May | Sadia Sharmin | Efficient Counting of Maximal Independent Sets in Sparse Graphs |

26 April | Arvid Lundervold | The role of graph theory and network analysis in quantitative neuroimaging |

19 April | Emilio Coppa | From asymptotics to performance profiling (and back) |

12 April | < No seminar > | |

5 April | M. S. Ramanujan | Backdoors to Satisfiability via q-horn formulas |

29 March | Easter holiday | |

22 March | Jean-François Couturier | A tight bound on the number of minimal dominating sets in split graph |

15 March | Dimitrios M. Thilikos | Polynomial gap extensions of the Erdős-Pósa theorem |

8 March | Henning Fernau | A multivariate analysis of pattern language problems |

1 March | Daniel Meister | Recent developments in clique-width computation |

22 February | Winter School 2013 | |

15 February | Rémy Belmonte | Graph rewriting |

8 February | Yixin Cao | Interval Deletion is Fixed-Parameter Tractable |

1 February | Rémy Belmonte | Induced Immersions |

25 January | Sven Simonsen | The complexity of finding arc-disjoint spanning trees and branchings in digraphs. FPT approach. |

18 January | Daniel Lokshtanov | Near-Tight Bounds for Cross-Validation via Loss Stability |

11 January | < No seminar > |

## 2012

**Høstsemesteret 2012**

The algorithm group is inviting everyone to attend the Algorithms seminar series, where we meet every **Friday**. We start with lunch at 12.00, and the seminar starts at **12.45**, unless otherwise specified. The lunch is in the algorithm library and the seminar is in room 3137.

In charge of the seminars is Pål Grønås Drange. Any question can be directed to Pal.Drange@ii.uib.no.

14 December | Archontia Giannopoulou | Lifo-search on (Di)graphs |

7 December | Pinar Heggernes | The maximum number of feedback vertex sets in chordal graphs and cographs |

5 December* | Hans Bodlaender | Connectivity problems on graphs of small treewidth |

30 November | Hans Bodlaender | Preprocessing and kernelization for Treewidth and Pathwidth |

23 November | Fedor V Fomin | Subexponential Parametrized Algorithm for Cluster Editing |

16 November | Reza Saeidinvar | Ramsey Numbers for Line Graphs and Perfect Graphs |

9 November | Erik Jan van Leeuwen | Parameterized Complexity of Induced H-Matching on Claw-Free Graphs |

2 November | Janne Korhonen | Counting in Halves and Fast Monotone Summation over Disjoint Sets |

26 October | Pim van 't Hof | On the parameterized complexity of finding separators with non-hereditary properties |

19 October | Ivan Bliznets | A new algorithm for parametrized MAX-SAT |

12 October | Daniel Lokshtanov | Polynomial Kernel for Planar F-Deletions |

5 October | Ignasi Sau | Parameterized domination in circle graphs |

28 September | Michał Pilipczuk | Randomized contractions |

21 September | Yngve Villanger | Searching for better fill-in |

14 September | Martin Vatshelle | The Point-Set Embeddability Problem for Plane Graphs |

7 September | Frederic Dorn | Short-term hydro scheduling from the algorithmic perspective |

3 September* | Bruce Reed | Catching a Drunk Miscreant |

31 August | Henning Fernau | Saving on Phases: Parameterized Approximation for Total Vertex Cover |

24 August | Rajesh Chitnis | Directed Multiway Cut is FPT |

17 August | Jan Arne Telle | FPT algorithms for domination in biclique-free graphs |

* means a special occasions seminar held outside of the general Friday seminar framework. 3rd of September, Bruce Reed visited our group in the occasion of Martin Vatshelle's PhD defence. He was so kind as to give a talk on recent work. 5th of December, during Hans Bodlaender's visit to Fedor Fomin's group, he gave a presentation of some of his recent work.

### Vårsemesteret 2012

This semester our algorithms seminar is on Fridays, as usual.

In charge of the seminars is Rémy Belmonte.

-- The seminar is in room **3137** at 12:45 unless otherwise specified.

-- We start with lunch at 12:00 (library).

22 May | Peter Golovach | Induced Disjoint Paths in AT-free Graphs |

8 June | Martin Vatshelle | Lower bounds on treewidth for practical computing (trial lecture) |

1 June | Mini-school on Width-Minors-Matroids | |

25 May | Arash Rafiey | Ordering without bad patterns |

11 May | Rémy Belmonte | Open problems session |

27 April | Michał Pilipczuk | On group feedback vertex set parameterized by the size of the cutset |

30 March | Igor Semaev | From Jacob Bernoulli to Modern Cryptography |

23 March | Bengt Aspvall | Sorting Algorithms As Special Cases Of A Priority Queue Sort |

16 March | Pim van 't Hof | Obtaining a Bipartite Graph by Contracting Few Edges |

9 March | Arash Rafiey | Homomorphism Problem and Approximation |

2 March | Michał Pilipczuk | Open problems session |

24 February | Finse | 10th Annual Winter School in Algorithms, Graph Theory, and Combinatorics |

17 February | Pål Grønås Drange | A randomized polynomial kernel for Odd Cycle Transversal |

10 February | Sigve H. Sæther | Broadcast domination on block graphs |

3 February | Martin Milanic | On the (in-)approximability and exact algorithms for vector domination and related problems in graphs |

20 January | Jean-Francois Couturier | Maximum number of minimal dominating sets in graph classes |

13 January | Erik Jan van Leeuwen | Algorithms for firefighting |

6 January | Daniel Lokshtanov | Faster Vertex Cover above LP |

## 2011

### Høstsemesteret 2011

This semester our algorithms seminar is on Fridays, as usual.

In charge of the seminars is Jesper Nederlof.

-- The seminar is in room **3137** at 12:45 unless otherwise specified.

-- We start with lunch at 12:00 (library).

16 December | Rémy Belmonte | Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths |

9 December, 10.15, Large Auditorium!! | Jesper Nederlof | Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms (PhD dissertation) |

2 December | Michał Pilipczuk | Solving the 2-Disjoint Connected Subgraphs problem faster than 2^n |

joint work with Marek Cygan, Marcin Pilipczuk and Jakub Onufry Wojtaszczyk
| ||

25 November, At 10.15, Small Auditorium!! | Jesper Nederlof | Property testing (Trial lecture) |

18 November | Henning Fernau | Parameterized Approximation Algorithms for Hitting Set |

Abstract Several techniques have been developed over the years for (polynomial-time) approximation algorithms and for parameterized algorithms. We will show how to employ and combine some of these in order to obtain both new polynomial-time approximation algorithms for some types of Hitting Set problems as well as approximation algorithms that use exponential time in cases where polynomial-time algorithms with certain approximation guarantees are not to be expected under some complexity-theoretic assumptions. The polynomial-time algorithm that I will present is based on reduction rules, a technique primarily developed in the area of parameterized algorithms, while the (exponential-time) approximation algorithms combines ideas from approximation (namely, local ratio techniques) with search-tree algorithms. | ||

11 November | Daniel Paulusma | Lift Contractions |

Joint work with: Petr Golovach, Marcin Kaminski and Dimitrios Thilikos
| ||

4 November | Ruben van der Zwaan | Preemptive and Non-Preemptive Generalized Min Sum Set Cover |

Abstract This talk is based on joint work with Sungjin Im and Maxim Sviridenko, where we give a 2-approximation for the Preemptive Generalized Min Sum Set Cover and use this to improve the current best approximation algorithm for Generalized Min Sum Set Cover. The problem was introduced by Azar, Gamzu and Yin, who gave a O(log n) approximation, which was improved by Bansal, Gupta and Krishnaswamy to roughly 500 and very recently to 28 by Skutella and Williamson.In this talk I will motivate why this is an interesting problem to look at, for example both broadcast scheduling and web search ranking can be modelled as Generalized Min Sum Set Cover. Further, why it makes sense to look at the Preemptive version of the problem. I will not give proofs in this talk, I will just highlight the main ingredients needed to obtain this 2-approximation for the preemptive problem and later show how to transform this into a non-preemptive solution. At the end, I will possibly say something on generalizing this problem by using submodular cost functions, but only if time permits. | ||

28 October | Bart Jansen | Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization |

Abstract In an informal blackboard-talk I will describe some results of a recent paper at ICALP, where we studied whether efficient preprocessing schemes for the Treewidth problem can give provable bounds on the size of the processed instances using the framework of kernelization. Assuming the AND-distillation conjecture to hold, the standard parameterization of Treewidth does not have a kernel of polynomial size and thus instances (G, k) of the decision problem of Treewidth cannot be efficiently reduced to equivalent instances of size polynomial in k. We therefore consider different (structural) parameterizations of the Treewidth problem. We show that Treewidth has a kernel with O(l^3) vertices, with l the size of a vertex cover, and a kernel with O(l^4) vertices, with l the size of a feedback vertex set. I will try to share some insights into how the reduction rules were found, and their relationship to experimental work on preprocessing heuristics for treewidth. We also obtained various kernel lower-bounds. Treewidth parameterized by the vertex-deletion distance to a co-cluster graph and Weighted Treewidth parameterized by the size of a vertex cover do not have polynomial kernels unless NP \subseteq coNP/poly. Treewidth parameterized by the deletion distance to a cluster graph has no polynomial kernel unless the AND-distillation conjecture does not hold. If time permits I will show which properties of treewidth were exploited in the reductions that yield these lower-bounds. | ||

21 October | Petteri Kaski | Fast zeta transforms for lattices with few irreducibles |

Abstract We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius algebras of finite lattices. We show that every lattice with $v$ elements, $n$ of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size $O(vn)$ for computing the zeta transform and its inverse, thus enabling fast multiplication in the Möbius algebra. | ||

14 October | No Seminar | |

7 October | Michał Pilipczuk | Problems parameterized by treewidth tractable in single exponential time: a logical approach |

Abstract We introduce a variant of modal logic, dubbed EXISTENTIAL COUNTING MODAL LOGIC (ECML), which captures a vast majority of problems known to be tractable in single exponential time when parameterized by treewidth. It appears that all these results can be subsumed by the theorem that model checking of ECML admits an algorithm with such complexity. We extend ECML by adding connectivity requirements and, using the Cut&Count technique, prove that problems expressible in the extension are also tractable in single exponential time when parameterized by treewidth; however, using randomization. The need for navigational character of the introduced logic is informally justified by a negative result that two expository problems involving non-acyclic conditions, C_l-VERTEX-DELETION and GIRTH>l-VERTEX-DELETION for l>=5, do not admit such a robust algorithm unless Exponential Time Hypothesis fails. | ||

30 September | Fedor Fomin | Linear kernels for dominating set on H-minor-free graphs |

23 September | Ramanujan Maadapuzhi Sridharan | A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments |

Abstract In the {\sc $k$-Feedback Arc/Vertex Set} problem we are given a directed graph $D$ and a positive integer $k$ and the objective is to check whether it is possible to delete at most $k$ arcs/vertices from $D$ to make it acyclic. Dom et al.[{\em CIAC, 2006}\,] initiated a study of the {\sc Feedback Arc Set} problem on bipartite tournaments ({\sc $k$-FASBT}) in the realm of parameterized complexity. They showed that {\sc $k$-FASBT} can be solved in time $O(3.373^k n^6)$ on bipartite tournaments having $n$ vertices. However, until now there was no known polynomial sized problem kernel for {\sc $k$-FASBT}. In this paper we obtain a cubic vertex kernel for {\sc $k$-FASBT}. This completes the kernelization picture for the {\sc Feedback Arc/Vertex Set} problem on tournaments and bipartite tournaments. We obtain our kernel using a non-trivial application of ``independent modules'' which could be of independent interest. | ||

Thursday 15 September (with lunch at 12 as usual) | Saket Saurabh | Surprise talk |

9 September | No seminar due to IPEC 2011 | |

2 September | No seminar due to WORKER 2011 | |

26 August, At 10.30!! | Daniel Lokshtanov | Outlier Detection for DNA Fragment Assembly |

Joint work with Christina Boucher and Christine Lo, UCSD
- Under the natural assumption that the number of outliers k is small, the PTAS for the distance minimization version of Consensus String with Outliers performs very well. In particular, as long as k <= n/2 the algorithm provides a (1+e) approximate solution in time f(1/e)(nL)^{O(1)} and thus is an EPTAS. - In order to improve the PTAS for Consensus String with Outliers to an EPTAS, the assumption that k is small is necessary. Specifically, when k is allowed to be arbitrary the Consensus String with Outliers problem does not admit an EPTAS unless FPT=W[1]. - The decision version of {\em Consensus String with Outliers} is fixed parameter tractable when parameterized by d/(n-k). and thus, also when parameterized by just d. To the best of our knowledge, Consensus String with Outliers is the first problem that admits a PTAS, is fixed parameter tractable when parameterized by the value of the objective function, but which provably does not admit an EPTAS under plausible complexity assumptions. To accommodate for this our hardness of approximation proof needs to combine parameterized reductions and gap preserving reductions in a novel manner. | ||

19 August | André Nichterlein | On Tractable Cases of Target Set Selection |

Complementing results on its approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters "diameter", "cluster editing number", "vertex cover number", and "feedback edge set number" of the underlying graph on the problem's computational complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains W[2]-hard with respect to the parameter "size of the target set". TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number. Both results contrast known parameterized intractability results for the parameter treewidth. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter cluster edge deletion number, yielding tractability for certain dense networks. |

### Vårsemesteret 2011

This semester our algorithms seminar is on Fridays, as usual.

In charge of the seminars is Pim van 't Hof.

-- The seminar is in room **3137** at 12:45 unless otherwise specified.

-- We start with lunch at 12:00 (library).

17 June | Reza Saei | Some Topics on Domination |

10 June | (Minicourse by Patrice Ossona de Mendez) | |

27 May | Serge Gaspers | Kernels for Global Constraints |

20 May | (Treewidth Workshop) | |

13 May | Petr Golovach | Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees |

29 April | Pim van 't Hof | Contracting Graphs to Paths and Trees |

22 April | (Easter Break) | |

15 April | Daniel Meister | Induced Subgraph Isomorphism on Two Classes of Perfect Graphs |

8 April | Erik Jan van Leeuwen | PTAS for Weighted Set Cover on Unit Squares |

1 April | Johannes Langguth | Sequential and Parallel Algorithms for Bipartite Matching |

25 March | Marek Cygan | The Stubborn Problem is Stubborn No More |

18 March | Yuri Rabinovich | On Complexity of the Sub-Pattern Problem |

11 March | Fredrik Manne | Efficient Self-Stabilizing Graph Searching in Trees |

4 March | Jan Arne Telle | Locally Constrained H-Homomorphism on Graphs of Logarithmic Boolean-Width |

25 February | (Winter School) | |

18 February | Sven Köhler | Fault-Containing Self-Stabilization in Asynchronous Systems with Constant Fault-Gap |

11 February | Dimitrios Thilikos | Deciding More Containment Relations in Embedded Graphs in FPT Time |

4 February | Bengt Aspvall | Utforske Matematikk fra IKT (Uten Bruk av Datamaskin) - Departmental seminar, 13:15-15:00, Lille Auditorium, SV-bygget |

28 January | Thomas Ågotnes | Normative State Transition Systems: Logic, Games and Complexity |

7 January | Bart Jansen | Vertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter |

## 2010

### Høstsemesteret 2010

This semester our algorithms seminar is back on Fridays, as usual.

In charge of the seminars is Erik Jan van Leeuwen.

-- The seminar is in room **3137** at 12:45 unless otherwise specified.

-- We start with lunch at 12:00 (library).

3 December | Jan Arne Telle | Social Networks |

26 November | Lisa Schreiber | The Unbounded Knapsack Problem and the Generalized Cordel Property |

19 November | Geevarghese Philip | t-Total Vertex/Edge Cover: Fixed Parameter Tractability and Kernelization Complexity |

5 November | Fran Rosamond | On the Complexity of Some Constraint Satisfaction Problems with Global Constraints and Convexity |

29 October | Danny Hermelin | Minimum Vertex Cover in Rectangle Graphs |

15 October | Binh-Minh Bui-Xuan | Recipe for computing generalisations of modular decomposition |

8 October | Neeldhara Misra | Connected Dominating Set and Short Cycles |

1 October | Mike Fellows | Why vote? |

24 September | Frederic Dorn | Fast Minor Testing in Planar Graphs |

17 September | Martin Vatshelle | Faster Algorithms on Branch and Clique Decompositions |

10 September | Saket Saurabh | Parameterized Problems that have Slightly Superexponential Time Algorithms |

3 September | Frank Kammer | Approximate Tree Decompositions of Planar Graphs in Linear Time |

27 August | Frank Kammer | Disjoint Paths on Chordal Graphs |

20 August | Daniel Lokshtanov | Clustering with Local Restrictions |

### Vårsemesteret 2010

This semester we had to move our algorithms seminar to Thursdays instead of Fridays, since several members of the group have Norwegian course on Fridays.

In charge of the seminars is Binh-Minh Bui-Xuan.

-- The seminar is in room **3137** at 12:45 unless otherwise specified.

-- We start with lunch at 12:00 (library).

17 June | Yahav Nussbaum | Maximum Flow in Directed Planar Graphs with Vertex Capacities |

10 June | Pinar Heggernes | Generalized graph clustering: recognizing (p,q)-cluster graphs |

3 June | Rémy Belmonte | On classes of graphs with logarithmic boolean-width |

27 May | Dieter Kratsch | Colorings with few colors |

6 May | Michel Habib | On the computation of 2-join |

29 April | Erik Jan van Leeuwen | Parameterized approximability: EPTAS and beyond |

8 April | Daniel Meister | About the existence of good digraph width measures |

25 March | Mostofa Patwary | Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure |

18 March | Petr Golovach | Cops and Robber Game Without Recharging |

11 March | Pierre Fraigniaud | Compact Ancestry Schemes and Small Universal Posets |

25 February | (Winter School) | |

18 February | Johannes Langguth | A parallel algorithm for bipartite matching |

11 February | Jesper Nederlof | Saving Space by Algebraization 2 |

4 February | Daniel Lokshtanov | Known Bounded Treewidth Algorithms are (Probably) Optimal |

28 January | Mamadou Kanté | Rank-width of edge-colored graphs |

21 January | Nicolas Bourgeois | Approximating with moderately exponential algorithms |

15 January | Frederic Dorn | A faster FPT-algorithm for Planar Subgraph Isomorphism |

## 2009

### Høstsemesteret 2009

In charge of the seminars is Yngve Villanger.

-- The seminar is in room **3137** at 12:45 unless otherwise specified.

-- We start with lunch at 12:00 (library).

11 December | Jean Blair | Discovering Open Graph Theoretic Problems Motivated by Network Science |

4 December | Johan van Rooij | Exact Algorithms for Edge Domination |

27 November | Pim van 't Hof | Computing Role Assignments of Chordal Graphs |

20 November | Daniel Lokshtanov | Saving Space By Algebraization |

6 November | Pinar Heggernes | Linear clique-width of some proper interval graphs |

30 October | Rodica Mihai | Edge search number of cographs in linear time |

23 October | 25th anniversary of Department of informatics | |

16 October | GROW 2009 | |

9 October | Michaël Rao | Last Cases of Dejean's Conjecture |

2 October | Fedor V. Fomin | Local Search: Is brute-force avoidable? |

25 September | Abhijin Adiga | Lower Bounds for Boxicity |

18 September | Jean Blair | An Efficient Self-stabilizing Distance-2 Coloring Algorithm |

4 September | Paul Bonsma | Finding fullerene patches in polynomial time |

28 August | Sourav Chakraborty | Market Equilibrium with Transaction Costs |

21 August | Yuri Rabinovich | On Cut Dimension of a Metric Space |

### Vårsemesteret 2009

In charge of the seminars is Daniel Meister.

-- The seminar is in room **3137** at 12:45 unless otherwise specified.

-- We start with lunch at 12:00 (3137 or library).

19 June | Jesper Nederlof | Möbius inversion 2 |

12 June | Jesper Nederlof | Möbius inversion |

5 June | Daniel Meister | Chordal digraphs |

29 May | Mostofa Ali Patwary | A Scalable Parallel Union-Find Algorithm for Distributed Memory Computers |

22 May | Saket Saurabh | 3k-Vertex Kernel for Maximum Internal Spanning Tree |

15 May | Venkatesh Raman | Polynomial Kernel for Dominating Set on Graphs of Bounded Degeneracy |

8 May | Dieter Kratsch | Convex Recoloring Revisited |

24 April | Andrzej Proskurowski | Modeling computer/communication networks |

17 April | Daniel Lokshtanov | Hypergraph Max-Cut Meets Hypergraph Spanning Tree |

3 April | Holger Dell | Sparsification Lower Bounds |

27 March | Isolde Adler | The homomorphism problem for structures |

20 March | Binh-Minh Bui-Xuan | Need-For-Speed (on the track of an optimal rankwidth decomposition: pros and cons) |

6 March | Pınar Heggernes | A guided tour to İstanbul |

27 February | Saket Saurabh | Kernelization - A Current View Point |

20 February | Petr Golovach | Guarding games on graphs |

13 February | Morten Mjelde | PhD defence |

6 February | Daniel Lokshtanov | Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves |

30 January | Tınaz Ekim | Polar graphs |

23 January | Isolde Adler | Computing excluded minors |

16 January | Sang-il Oum | Maximum number of complete subgraphs in a certain graph |

9 January | Yngve Villanger | Faster parameterized algorithms for Minimum Fill-in |

## 2008

### Høstsemesteret 2008

In charge of the seminars is Johannes Langguth.

-- The seminar is in room **2143** at 13:00 unless otherwise specified.

-- We start with lunch at 12:15 in the third floor (3137 or library).

12 December | Jesper Nederlof | Inclusion-exclusion for hard problems |

28 November | Ioan Todinca | |

21 November | Ruben van der Zwaan | Vertex ranking |

14 November | Haiko Müller | On a Disparity Between Relative Cliquewidth and Relative NLC-width |

7 November | Binh-Minh Bui-Xuan | On speeding up divide-and-conquer algorithms: making faster unifications or doing less conquests? |

31 October | Matthias Mnich | Computing a Maximum Agreement Supertree |

17 October | Federico Mancini | Clustering with partial information |

10 October | Jan Arne Telle | The Bergen Graph Parameter Project, a proposal for discussion |

3 October | Michal Walicki | Kernels of digraphs |

26 September | Daniel Lokshtanov | Graph Layout Problems Parameterized by Vertex Cover |

19 September | Michel Habib | Minimal separators and maximal cliques in chordal graphs revisited starts 11:00 in room 3137 |

12 September | Petr Golovach | A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs |

5 September | Serge Gaspers | Iterative Compression and Exact Algorithms |

22 August | Federico Mancini | Algorithms for search engines (prøveforelesing) starts 13:15 in room 2142 |

### Vårsemesteret 2008

In charge of the seminars is Morten Mjelde.

-- The seminar is at room **3137** at 13.00.

8 February | Binh-Minh Bui-Xuan | Tree-representation of set families and graph decompositions |

15 February | Petr Golovach | Generalized domination in degenerate graphs: ambivalence and complexity |

22 February | Serge Gaspers | Cleaning and Protecting a Graph |

29 February | Morten Mjelde | Temporal Partition in Sensor Networks. |

7 March | Johannes Langguth | Market Equilibria |

14 March | Joanna Bauer | Dissertation |

28 March | Michael Fellows | Correlation Clustering, Graph Separation, and Removing Necklaces: A Tale of Equivalent Open Problems |

4 April | Mikko Koivisto | Exponential-time algorithms for Bayesian networks |

11 April | Daniel Lokshtanov | Cutwidth of split graphs, threshold graphs, and proper interval graphs |

18 April | Gregori Sorkin | Faster solving, counting, and sampling |

25 April | Saket Saurabh | Finding sub graphs whose matching number equals its minimum vertex cover number |

9 May | Petteri Kaski | Deletion--contraction invariants and fast subset convolution |

23 May | Marc Bezem | Shortest paths in hypergraphs |

30 May | Frederic Dorn | An FPT Algorithm for Directed Spanning k-leaf |

6 June | Yngve Villanger | Computing treewidth with a help of firefighters |

13 June | Jan Arne Telle | H-join graphs and rankwidth |

20 June | Lene Monrad Favrholdt | Comparing First-Fit and Next-Fit for Online Edge Coloring |

27 June | Sushmita Gupta | Feedback Art set problem in bipartite tournaments |

## 2007

### Høstsemesteret 2007

In charge of the seminars is Daniel Lokshtanov.

-- Every Friday we have Algorithms seminar in Room **2143** at 12:30.

30 November | Petr Golovach | On tractability of Cops and Robbers game |

14 September | Frederic Dorn | Dissertation |

7 September | Fedor Fomin | Parameterized subexponential algorithms |

31 August | Yngve Villanger | Improved parameterized algorithms for feedback vertex set problem |

### Vårsemesteret 2007

In charge of the seminars is Federico Mancini.

-- Every Friday we have Algorithms seminar in Room **2143** at 12:30.

-- Every Friday we have Algorithms lunch at the library on the 3rd floor at 11:45.

15 June | Feodor Dragan | Distance and Routing Labeling Schemes in Graphs with Applications |

8 June | R. Sritharan | 4-leaf powers: structure and recognition |

1 June | Yngve Villanger | k-interval completions |

1 June | Moritz Mueller | Parameterized Analogues of the Valiant- Vazirani Lemma |

25 May | Danny Hermelin | Lower bounds for kernelization |

18 May | Petr Golovach | Computational complexity of generalized domination for chordal graphs |

11 May | Qin Xin | Faster treasure hunts and better strongly universal exploration sequencestd> |

4 May | - | Research school |

27 April | Elena Losievskaja | Approximation algorithms for the Maximum Independent set problem in hypergr aphs |

20 April | Mike Fellows | Parameterization of complexity is all about structure theory, and how to use it |

13 April | Dimitrios M. Thilikos | Graph Searching in a Crime Wave |

30 March | Rodica Mihai | Mixed search number and linear-width of interval and split graphs |

23 March | Charis Papadopulos | Single-edge monotonic sequences of graphs |

16 March | Mathieu Liedloff | An exact algorithm for the minimum dominating clique problem |

9 March | Morten Mjelde | Self-stabilizing matching |

2 March | -------- | Winter holidays break |

23 February | Alexey Stepanov | Counting Dominating Sets |

16 February | Fedor Fomin | On Self Duality of Pathwidth in Polyhedral Graph Embeddings |

9 February | Fredrik Manne | New Star and Acyclic Coloring Algorithms |

2 February | Saket Saurabh | Parameterized complexity of Directed Max Leaf |

26 January | Yngve Villanger | Characterizing minimal interval completions |

## 2006

### Høstsemesteret 2006

In charge of the seminars is Serge Gaspers.

-- On announced Fridays we have Algorithms seminar in Room **2142** at 12:30.

-- Every Friday (regardless of whether there is a seminar afterwards)

we have Algorithms lunch at the HIB cafeteria at 11:45

(everybody is welcome to join).

15 December | Qin Xin | Faster Centralized Communication in Radio Networks |

8 December | Daniel Meister | Computing treewidth and minimum fill-in for permutation graphs in linear time |

1 December | Serge Gaspers | Branching and Treewidth Based Exact Algorithms |

24 November | Omid Amini | Minimal Selectors and Fault Tolerant Networks |

17 November | Jan Arne Telle | On the crossing number of graphs with an excluded minor |

10 November | Prudence Wong | Energy Efficient Online Deadline Scheduling |

3 November | Morten Mjelde | A Memory Efficient Self-stabilizing Algorithm for Maximal k-packing |

27 October | Charis Papadopoulos | Making arbitrary graphs transitively orientable: Minimal comparability completions |

20 October | Daniel Lokshtanov | Determining treelength is hard (Treelength has been introduced in this paper) |

6 October | Parameterized Complexity of Dominating Set | |

29 September | Gregory Gutin | Parameterized Complexity for Graph Linear Arrangement Problems (abstract) |

22 September | Federico Mancini | A completely dynamic algorithm for split graphs |

8 September | Magnus Wahlström | Approaches to a #2SAT algorithm analysis |

1 September | Frederic Dorn | Dynamic Programming and Fast Matrix Multiplication |

28 August | Sbastien Tixeuil | Self-stabilization |

### Vårsemesteret 2006

In charge of the seminars is Frederic Dorn.

-- On announced Fridays we have Algorithms seminar in Room **2143** at

12:30.

-- Every Friday (regardless of whether there is a seminar afterwards)

we have Algorithms lunch at the HIB cafeteria at 11:45

(everybody is welcome to join).

2 June | Qin Xin | Optimal Gossiping with Unit Size Messages in Known Topology Radio Networks |

19 May | Christophe Paul | Algorithmic aspects of modular decomposition |

5 May | Herman Ruge Jervell | Wellordering finite trees (abstract) |

28 April | Hans Bodlaender | On Exact Algorithms for Treewidth |

31 March | Dieter Kratsch | Lower Bounds for Exact Maximum Independent Set Algorithms |

24 March | Artem Pyatkin | On polynomial algorithms on the vector sum problem |

17 March | Ioan Todinca | Proper interval graphs: a minimal completion algorithm (abstract) |

10 March | Federico Mancini | Minimal Split Completions of Graphs |

3 March | Frederic Dorn | Two birds with one stone: the best of branchwidth and treewidth with one algorithm |

24 February | Yngve Villanger | Improved Exponential-time Algorithms for Treewidth and Minimum Fill-in |

17 February | Saket Saurabh | Parameterized algorithms for finding feedback vertex set |

10 February | Eva-Marta Lundell | Subexponential-time framework for optimal embeddings of graphs in integer lattices |

3 February | Jan Kratochvil | Distance constrained graph labeling and graph homomorphisms |

27 January | Fredrik Manne | Parallel graph coloring for distributed memory computers |

20 January | Serge Gaspers | Exponential algorithms for the Maximum P_3-free Induced Subgraph Problem |

13 January | Fabrizio Grandoni | Exponential time algorithm for Independent Set: Measure & Conquer |

## 2005

### Høstsemesteret 2005

In charge of the seminars is Alexey (Ljosha) Stepanov.

-- On announced Fridays we have Algorithms seminar in Grupperom **2101** at

12:30.

-- Every Friday (regardless of whether there is a seminar afterwards)

we have Algorithms lunch at the HIB cafeteria at 11:45

(everybody is welcome to join).

18 November | Qin Xin | Faster Communication in Ad-hoc Radio Networks(abstract) |

11 November | Jan Arne Telle | New results on branchwidth of graphs |

4 November | Alexey Stepanov | Bounding the Number of Minimal Dominating Sets: a Measure and Conquer Approach |

14 October | Karol Suchan | Minimal interval completions |

7 October | Charis Papadopoulos | Drawing graphs using modular decomposition |

30 September | Frederic Dorn | Subexponential Algorithms for Planar Hamiltonicity |

23 September | Daniel Paulusma | Backbone coloring |

16 September | Fedor Fomin | On pathwidth of 3-regular graphs |

9 September | Jiri Fiala | Degree structure of a graph and degree matrices (abstract) |

2 September | Pinar Heggernes | Exact algorithms for graph homomorphisms |

### Vårsemesteret 2005

In charge of the seminars is Alexey (Ljosha) Stepanov.

-- On announced Fridays we have Algorithms seminar in Grupperom 2104 at

12:30.

-- Every Friday (regardless of whether there is a seminar afterwards)

we have Algorithms lunch at the HIB cafeteria at 11:45

(everybody is welcome to join).

10 June | Daniel Lokshtanov | Optimal broadcast domination of arbitrary graphs in polynomial time |

22 April | Artem Pyatkin | On maximum number of minimal dominating sets in graphs |

15 April | Dimitrios Thilikos | Faster fixed-parameter tractable algorithms for matching and packing problems (abstract) |

8 April | Marina Lipshteyn | Representations of Edge Intersection Graphs of Paths in a Tree (abstract) |

11 March | Dieter Kratsch | The use of modular decomposition to design linear time algorithms for (P_5,gem)-free graphs (abstract) |

4 March | Pierre Fraigniaud | A New Perspective on the Small-World Phenomenon: Greedy Routing in Tree-Decompositions |

4 February | Alexey Stepanov | Quasiconvex Analysis of Backtracking Algorithms |

28 January | Di Yuan | Optimization of Pilot Signal Power in WCDMA Networks |

## 2004

### Høstsemesteret 2004

In charge of the seminars is Frederic Dorn.

Fridays 12:30 (etter algoritmelunsj

11:45 i HIB kantinen) Grupperom 2103.

17 Deceember | Elias Dahlhaus | Converting a nested dissection algorithm into a minimal elimination algorithm |

10 December | Yngve Villanger | Computing minimal triangulations in time O(n log n) = o(n2.376) |

3 December | Joanna Bauer | Minimizing the energy for broadcasting in wireless networks |

12 November | Frederic Dorn | Comparing tree decompositions with branch decompositions |

29 October | Artem Pyatkin | On (k,l)-coloring of incidentors |

15 October | Anne Berry | Recognizing probe chordal graphs |

### Vårsemesteret 2004

In charge of the seminars is Fedor Fomin.

Fridays 12:30 (etter algoritmelunsj

11:45 i HIB kantinen) Grupperom 2104.

7 May | Jan Kristian Haugland | Regulare induserte undergrafer av gittere uten korte sykeler |

30 April | Fredrik Manne | Efficient multi-stage self-stabilizing algorithms on tree networks |

22 April | Ioan Todinca | Computing the treewidth for graphs with "few" minimal separators |

18 March | Fedor Fomin | Exact algorithms for treewidth |

11 March | Fedor Fomin | A Simple and Fast Approach for Solving Problems on Planar Graphs |

20 February | Dag Haugland | A tree decomposition approach to MI-FAP |

13 February | Bjørge Solli | David Eppstein's paper on Small Maximal Independent Sets and Faster Exact Graph Coloring |

13 February | Finse Winterschool Feedback | |

30 January | Elena Prieto | Method of coordinatized kernels on the bipartite subgraph problem |

## 2003

### Høstsemesteret 2003

In charge of the seminars is Fedor Fomin.

Fridays 12:30 (etter algoritmelunsj

11:45 i HIB kantinen) Grupperom 2104.

11 Decem)er | Dimitrios M. Thilikos | On the Monotonicity of Games Generated by Symmetric Submodular Functions |

7 November | Yngve Villanger | A vertex incremental approach to maintaining chordal graphs dynamically II |

31 October | Pierre Fraigniaud | Distributed Hash Tables for P2P Network |

30 October | Dieter Kratsch | Certifiying Algorithms |

24 October | Pinar Heggernes | The minimum degree heuristic and the minimal triangulation process |

17 October | Christian Sloper | New techniques in designing FPT-algorithms |

10 October | Christian Sloper | Using Vertex Cover Structure in designing FPT-algorithms - the case of k-Internal Spanning Tree |

3 October | Yngve Villanger | A vertex incremental approach to maintaining chordal graphs dynamically |

26 September | Jan Arne Telle | Catval graphs and the catwidth graph parameter |

5 September | Fedor Fomin | Fixed-Parameter Algorithms for the (k,r)-Center in Planar Graphs and Map Graphs |

29 August | Jan Arne Telle | Graph searching, elimination trees, and a generalization of bandwidth |

### Vårsemesteret 2003

In charge of the seminars is Fedor Fomin.

Hovedtema for semesteret er Exact algorithms for NP-hard problems

Fridays 12:15 Grupperom 2143.

15 May 2003 | Christian Schindelhauer | Worst Case Mobility in Ad Hoc Networks |

2 May 2003 | Fedor Fomin | Exact algorithms for NP-hard problems VII |

25 April 2003 | Pinar Heggernes | Broadcast domination for interval graphs and trees |

11 April 2003 | Fedor Fomin | Exact algorithms for NP-hard problems VI |

28 March 2003 | Hans Bodlaender | Treewidth k in linear time |

27 March 2003 | Hans Bodlaender | Treewidth: Heuristics and Preprocessing |

21 March 2003 | Fedor Fomin | Exact algorithms for NP-hard problems V |

14 March 2003 | Fedor Fomin | Exact algorithms for NP-hard problems IV |

28 February 2003 | Fedor Fomin | Exact algorithms for NP-hard problems III |

18 February 2003 | Frederic Dorn | LEDA & Tuning Algorithms for Hard Planar Graph Problems |

7 February 2003 | Fedor Fomin | Exact algorithms for NP-hard problems II |

24 January 2003 | Fedor Fomin | Exact algorithms for NP-hard problems |

## 2002

### Høstsemesteret 2002

In charge of the seminars is Fredrik Manne.

Fridays 12:15 Grupperom 2101.

29 November 2002 | Jan Arne Telle | Planar graphs and treewidth II |

22 November 2002 | Jan Arne Telle | Planar graphs and treewidth I |

8 November 2002 | Fredrik Manne | A Linear time 2-approximation algorithm for maximum weighted matching in general graphs |

25 October 2002 | Leda-gruppen | Introduksjon til Leda |

18 October 2002 | Pinar Heggernes | Maximum Cardinality Search for Minimal Triangulations |

4 October 2002 | Kjell Jørgen Hole | Algorithmic problems in mobile and ad-hoc networks |

27 September 2002 | Assefaw H. Gebremedhin | Parallel Distance-k Coloring Algorithms for Numerical Optimization |

13 September 2002 | Yngve Villanger | Efficient Implementation of a Minimal Triangulation Algorithm |

### Vårsemesteret 2002

In charge of the seminars is Jean Blair.

Fridays 12:15 Grupperom 2101.

8 February 2002 | Jan Kratochvil | Intersection graphs |

15 February 2002 | Jiri Fiala | The independence and coloring problems on disk graphs |

22 February 2002 | Ondra Pangrac | String graphs |

1 March 2002 | Jean Blair | Winter school impressions - AAR |

8 March 2002 | Petter Kristiansen | A self-stabilizing algorithm for maximal 2-packing |

15 March 2002 | Jan Arne Telle | Tree decompostions of small pathwith |

22 March 2002 | Jan Arne Telle | Tree decompostions of small pathwith (continued) |

5 April 2002 | Petter Kristiansen | Domination, independence, irredundance |

12 April 2002 | Jean Blair | Generalized vertex covers |

19 April 2002 | group work | Classes of graphs having vertex covers that are: K-partite, independent, c lique, or acyclic |

26 April 2002 | group work | Graphs with induced path and induced tree vertex covers |

3 May 2002 | group work | More on induced path and induced-tree vertex covers |

14 May 2002 | Fedor Fomin | Radio networks and graph colorings |

## 2001

### Høstsemesteret 2001

Dette semesteret har vi ikke algoritmeseminar siden det nye kurset

I238 g�r for f�rste gang med tema som er nye for de fleste.

Interesserte er velkommen til � delta

i deler av kurset.

### Vårsemesteret 2001

Dette semesteret har vi ikke algoritmeseminar siden vi gjennomg�r

utvalgte tema i algoritmer i I239. Interesserte er velkommen til

� f�lge med p� ulike deler av kurset.

## 2000

### Høstsemesteret 2000

Fredager 12:15 Grupperom 2103.

Hovedtema for semesteret er FPT - Fixed Parameter Tractability

Ansvarlig: Jan Arne Telle

8 September 2000 | Jan Arne Telle | Fixed parameter tractability (FPT) | |

15 September 2000 | Christian Sloper | FPT : Bounded search trees | |

22 September 2000 | Petter Kristiansen | FPT : Reduction to a problem kernel | |

29 September 2000 | Petter Kristiansen | FPT : List of interesting problems | |

6 Oktober 2000 | Christian Sloper | FPT: Planar red blue dominating set | |

20 Oktober 2000 | Petter Kristiansen | FPT : Graph modification problem | |

27 Oktober 2000 | Fredrik Manne | NM i programmering 2000 | |

3 November 2000 | Pinar Heggernes | FPT : Minimum fill is FPT | |

10 November 2000 | Christian Sloper | FPT: Method of test sets | |

17 November 2000 | Jan Arne Telle | Deterministic finite tree automata | |

24 November 2000 | Petter Kristiansen | Method of test sets for regular tree languages | |

1 Desember 2000 | Jan Arne Telle | Bounded degree parsing trees | |

8 Desember 2000 | Petter Kristiansen | Method of test sets on graphs with bounded treewidth |

## 1999

### Vårsemesteret 1999

Tema for semesteret: Grafalgoritmer for å minimere fyll

Ansvarlig: Pinar Heggernes

29/1 Magnus Halldorsson | Multicoloring of graphs |

5/2 Assefaw Hadish Gebremedhin | Parallell Graph Coloring |

12/2 Pinar Heggernes | Fyll: Hvorfor glissne matriser? |

19/2 Pinar | Fyll: Eliminasjonsordninger og fyll |

26/2 Jan Arne | Fyll: Kordale grafer I |

5/3 Jan Arne | Fyll: Kordale grafer II |

12/3 Jan Arne | Fyll: Kordale grafer III |

19/3 Utsatt | |

26/3 Petter Kristiansen | Pakking av grafer |

2/4 Påske | |

9/4 Fredrik Manne | Fyll: Min Degree og Nested Dissection |

16/4 Pinar Heggernes | Algoritmer for minimalt fyll |

23/4 Ole-Martin Kvinge | Grafalgoritmer for glisne matriser |

30/4 Anne Berry, Univ Montpellier, Frankrike | Algorithms for minimal fill |

7/5 Jan Kratochvil, Charles Univ, Prag, Tsjekkia | Partial covers of graphs |

14/5 Jiri Fiala, Charles Univ, Prag, Tsjekkia | Channel assignment problem |

21/5 Fredrik | Mer om fyll |

28/5 Knut Erstad | Visualisering ved hjelp av L-systemer |

31/5 Sidsel Horvei | Algoritmer for s�kemaskiner p� WWW |

## 1998

### Høstsemesteret 1998

Ansvarlig: Jan Arne Telle

11/9 Jan Arne Telle | Mod-2 Independence and domination in graphs |

18/9 Alex Pothen, Old Dominion Univ., USA | Graph Reductions: a theory of incomplete factorization |

25/9 Magnus Halldorsson, | Channel Assignment in Radio Networks (Partitioning Planar Graphs into Strong Stable Sets) |

2/10 Elias Dahlhaus, Univ. Ko"ln, Tyskland | Minimal elimination orderings of chordal graphs |

9/10 Andrzej Proskurowski, Univ. of Oregon, USA | Multisource shortest path problems |

16/10 Sven Sigurdsson, Science Institute, University of Iceland | Elimination trees in parameter estimation problems. |

23/10 Bengt Aspvall | Approximations for the general block distribution of a matrix |

30/10 Fredrik Manne, UiB | Strukturert Data Partisjonering |

20/11 Yngve Lamo, UiB, | Developing algorithms by calculation. (Topological Sorting: an example using relational calculus) |

4/12 Dieter Kratsch, Univ Jena, Tyskland | |

11/12 Pinar Heggernes | Partitioning a set of functions into correlated subsets |

Planar Contraction