Seminar

# 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.

## 2017

### Autumn 2017

The algorithms 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 13.00, unless otherwise specified.  The lunch is in the algorithms library and the seminar is in room 302O1.

In charge of the seminars is Paloma Lima.  Any question can be directed to Paloma (dot) Lima (at) ii (dot) uib (dot) no.

 22. Sept Sebastian Siebertz A tutorial on uniform quasi-wideness 15. Sept Mateus Oliveira Ground Reachability and Joinability in Linear Term Rewriting Systems are Fixed Parameter Tractable with Respect to Depth 08. Sept Roohani Sharma Sub-exponential Fixed-Parameter Tractable Algorithm for Directed Feedback Arc Set in a Special Class of Digraphs 01. Sept Lars Jaffke Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width 25. Aug Pranabendu Misra Bipartite Perfect Matching is in quasi-NC 18. Aug Ivan Mihajlin Irreducibility in fine-grained complexity

## 2016

### Autumn 2016

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 Akanksha Agrawal.  Any question can be directed to Akanksha (dot) Agrawal (at) ii (dot) uib (dot) no.

 02. Dec Marija Slavkovik Judgment aggregation and its complexity 25. Nov Pranabendu Misra Lossy Kernels for Graph Contraction Problems 18. Nov Pedro Montealegre Parameterized algorithms via minimal triangulations and potential maximal cliques 11. Nov Christophe Crespelle Linearity is Strictly More Powerful than Contiguity for Encoding Graphs 04. Nov Sanjukta Roy Stable Matching Games: Manipulation via Subgraph Isomorphism 28. Oct Amer E. Mouawad Packing Cycles Faster Than Erdős-Pósa 21. Oct Marcin Wrochna Algorithms for graphs and matrices in poly(tw)*n time 14. Oct Bart M. P. Jansen Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials 07. Oct Lars Jaffke Fine-Grained Parameterized Complexity Analysis of Graph Coloring 30. Sept Mateus de Oliveira Oliveira Tree-Zig-Zag Number of a digraph - Applications and Open Problems 23. Sept Md. Naim Community Detection on GPU 16. Sept PrafullKumar P Tale Dynamic Parameterized Problems 02. Sept Diptapriyo Majumdar Structural Parameterizations of Feedback Vertex Set

### Spring 2016

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 13.00, unless otherwise specified.  The lunch is in the algorithm library and the seminar is in room 3137.

In charge of the seminars is Torstein Strømme. Any questions can be directed to torstein (dot) stromme (at) ii (dot) uib (dot) no.

 Jun 10 Fichte/Charwat Jun 8(Wed) Junjie Ye Jun 2 (Thur) May 27 O-joung Kwon A single-exponential fixed parameter algorithm for Distance-Hereditary Vertex Deletion May 20 Daniel Lokshtanov Lower bounds for approximation schemes for Closest String May 13 Sushmita Gupta Stable matching games: Manipulation via graph connectivity May 6 Cancelled Apr 29 Department gathering Apr 22 Jan Arne Telle Apr 15 Edvin Berglin Applications of incidence in point covering problems Apr 8 Gunnar Fløystad The interplay between graphs, simplicial complexes and ring theory Apr 1 Mithilesh Kumar Component Order Connectivity Mar 25 Easter Vacation Mar 17 (Thur @ 14:15) Mateus de Oliveira Oliveira An Algorithmic Metatheorem for Graph Completion Problems Mar 11 Saket Saurabh Communication Complexity of Pairs of Graph Families with Applications Mar 4 M. S. Ramanujan A Linear Time Parameterized Algorithm for Feedback Vertex Set on Directed Graphs Feb 26 Fahad Panolan Editing to Connected f-Degree Graph Feb 19 Michal Walicki Kernels of Infinite Digraphs Feb 12 Petr Golovach Parameterized Complexity of Secluded Connectivity Problems Feb 5 Daniel Lokshtanov Below the Trivial Upper Bound for the Number of Minimal Connected Dominating Sets Jan 29 Cancelled Jan 22 Erik Parmann Case Studies in Constructive Mathematics (PhD defence) Jan 15 Damien Prot From classical (for me) to classical (for you) tools in scheduling theory Jan 8 Tarek R. Besold Like a Cognitive Walk in the Computational Park: Of  Atom Models and Foldable Toothbrushes Jan 6 Kitty Meeks When can an FPT decision algorithm be used to count?

## 2015

### Høstsemesteret 2015

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 Md Naim.  Any question can be directed to Md.Naim@uib.no

 11. Dec Magnus  Wahlstrom A combinatorial condition for FPT LP-branching 04. Dec Akanksha Agrawal 27. Nov Daniel Lokshtanov Parameterized Integer Quadratic Programming: Variables and Coefficients 20. Nov Amer Mouawad Simultaneous Feedback Vertex Set: A Parameterized Perspective 13. Nov Jan Arne Telle Recognizability equals definability for graphs of bounded treewidth and bounded chordality. 06. Nov No Seminar 30 Oct No Seminar 23. Oct Pål Grønås Drange Empirical hardness models: focusing on instance distributions representative of practical applications rather than worst-case. 19. Oct(Mon) Faisal Abu Khzam The Multi-Parameterized Cluster Editing 16. Oct Markus Sortland Dregi Compressing bounded degree graphs 09. Oct Pål Grønås Drange Editing to starforests and bicluster graphs in subexponential time. 02. Oct Diptapriyo Majumdar Kernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators 30. Sept(Wed) Meriav Zehavi Non-Standard Usage of the Method of Bounded Search Trees 25. Sept Torstein Strømme "Structural" kernelization for Vertex Cover. 18. Sept No Seminar 11. Sept Jan Arne Telle Max-matching-width: new characterizations and a fast algorithm for dominating set

### Vårsemesteret 2015

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 13.00, unless otherwise specified.  The lunch is in the algorithm library and the seminar is in room 3137.

In charge of the seminars is Fahad Panolan.  Any question can be directed to Fahad.Panolan@ii.uib.no.

 19.June Pranabendu Misra Deterministic Truncation of Linear Matroids 12.June Sudeshna Kolay Parameterized Algorithms for deleting to (r,l)-graphs 05.June Marcin Wrochna Recoloring graph homomorphisms using basic topology 29. May Reza Saei PhD defence 22. May Prof. Igor Semaev An application of combinatorics in cryptography 20. May (at 2 PM) Martin Koutecký Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth 15. May No seminar 13. May (at 2 PM) Kitty Meeks Parameterised Subgraph Counting Problems 08. May No seminar 01. May No seminar (Holiday) 24. April Reza Saei Graph spectra 17. April Jakub Gajarský MSO Logic on Trees of Bounded Height 10. April Prof.  Mike Fellow FPT is Extremal Gradients: A Partial Preview of an ERC Proposal 03. April No seminar (Holiday) 27. March Md. Naim GPU architecture and Graph Algorithm 20. March Dieter Kratsch Exact Exponential Algorithms 13. March Daniel Lokshtanov Subset Feed Back Vertex Set in O(25.6^k(|V(G)|+|E(G)|)) time 06. March Petr Golovach How to Hunt an Invisible Rabbit on a Graph 27. February Felix Reidl Structural sparsity in the real world 20. February Markus S. Dregi On the Computational Complexity of Vertex Integrity and Component Order Connectivity 13. February Rémy Belmonte Induced Minor Free Graphs: Isomorphism and Clique-width 06. February Akanksha Agrawal Vertex Cover on Delaunay Graphs 30. January M S Ramanujan A parameterized complexity dichotomy for Boolean QCSP Deletion 23. January Petr Golovach Editing to Eulerian Graphs 16. January Pål G. Drange Editing to Threshold Graphs

## 2014

### Høstsemesteret 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 Mithilesh Kumar.  Any question can be directed to Mithilesh.

 12.dec Christophe Crespelle A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph With Regard to the Cartesian Product 05.dec Daniel Lokshtanov Surprise !! 28.nov Saket Saurabh Solving Multicut faster than 2^n 21.nov Kristina Vuskovic Proof of the Confort-Rao Conjecture for linear balanced matrices 14.nov Isolde Adler PAC learning of FO definable concepts & nowhere dense graph classes 07.nov No Seminar 31.oct Sebastian Ordyniak Backdoors into Heterogeneous Classes of SAT and CSP 24.oct Open Problems Session 17.oct No Seminar 10.oct Sigve Sæther Between Treewidth and Clique-Width 03.oct Mithilesh Kumar Faster Feedback Vertex Set in Tournaments 26.sep Amer Mouawad Reconfiguration problems: Structure and tractability 19.sep Fahad P. Faster FPT Algorithm for Eulerian Edge Deletion 12.sep Ashutosh Rai On the kernelization complexity of String Problems 05.sep Reza Saei Reconfiguration graphs and problems 29. aug Sandeep  R.B. On Polynomial Kernelization of H-free Edge Deletion 22. aug NA No Seminar 15. aug Blair Sullivan Bringing Theory to the Real World: is structural sparsity realistic?

### 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.

 27. Juni No seminar 20. Juni Markus Dregi Parameterized Complexity of Bandwidth on Trees. 13. Juni Michael R. Fellows Parameterized Complexity AND Incremental Computing: some good news 6. Juni Daniel Lokshtanov Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth 30. May No seminar 23. May Alexey Stepanov Applications of TSP in real life 16. May Fabrizio Grandoni Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter 9. May Bart Jansen 2. May No seminar 25. April Rump Session 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 Fernando S Villaamil 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 Peter Bro Miltersen 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 Ariel Gabizon 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.

 13 December Geevarghese Philip Point Line Cover: The Easy Kernel is Essentially Tight 6 December Ioan Todinca Large Induced Subgraphs Via Triangulations and CMSO 29 November Christophe Paul Explicit Linear Kernels via Dynamic Programming 22 November Michał Pilipczuk PhD defense at 14:00 in room 2144 15 November Jan Arne Telle The graph formulation of the union-closed conjecture 8 November Archontia Giannopoulou Polynomial Kernel for Tree Deletion Set 1 November Rémy Belmonte PhD defense at 10:15 in room 2144 25 October Martin Vatshele Independent Set in Outerstring Graphs 18 October Ivan Bliznets Largest chordal and interval subgraphs faster than 2^n 11 October Pranabendu Misra Faster Exact Algorithms for Some Terminal Set Problems 4 October Øyvind Ytrehus Coding theory and graphs 27 September Daniel Lokshtanov Independent Set in P5-Free Graphs in Polynomial Time 20 September Bart Jansen On Sparsification for Computing Treewidth 13 September Mateus de Oliveira Oliveira Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs 06 September Marcin Pilipczuk Fast branching algorithm for Cluster Vertex Deletion 30 August Jan Arne Telle Upper bounds on boolean-width with applications to exact algorithms 23 August Felix Reidl Graph classes of bounded expansion 16August Pim Van 't Hof The price of connectivity for feedback vertex set

### 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.

 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.

 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 Abstract The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z1, Z2 , asks whether it is possible to find disjoint sets A1, A2, such that Z1\subseteq A1, Z2\subseteq A2 and A1, A2 induce connected subgraphs. While the naive algorithm runs in O*(2^n) time, solutions with complexity of form O((2−eps)^n) have been found only for special graph classes. In the paper we present an O(1.933^n) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2^n barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel. 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 Abstract We introduce a new containment relation in graphs: lift contractions. We say that a graph H is a lift contraction of G if H can be obtained from G by a sequence of edge lifts and edge contractions. The edge lift operation is defined as follows. Let e=uv and e'=uw be two different edges incident with the same vertex u in a graph G. The lift of e and e' removes e and e' from G and then adds the edge vw if v and w are nonadjacent. We show that a graph contains every n-vertex graph as a lift contraction, if (1) its treewidth is large enough, or (2) its pathwidth is large enough and it is 2-connected, or (3) its order is large enough and its minimum degree is at least 3. 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 onbipartite 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 Abstract A major impediment in the development of inexpensive, efficient, full genome sequencing is the large portion of erroneous reads produced by sequencing platforms. Error correction is the computational process that attempts to identify and correct these mistakes. Several classical stringology problems, including the Consensus String problem, are used to model error correction. However, a significant shortcoming of using these formulations is that they do not account for a few of the reads being too erroneous to correct; these outlier strings potentially have great effect on the solution, and should be detected and removed. We formalize the problem of error correction with outlier detection by defining the Consensus String with Outliers problem. Given a set S of n length-L strings, and parameters d and k, the objective in the Consensus String with Outliers problem is to find a subset S^* of S of size n-k and a string s such that \sum_{s_i \in S^*} d(s_i, s) <= d. Here d(x, y) denotes the Hamming distance between the two strings x and y. We prove the following results:  - The variant of Consensus String with Outliers where the number k of outliers is fixed and the total distance \sum{s_i \in S^*} d(s_i, s) is to be minimized admits a simple PTAS. Our PTAS can easily be modified to also handle the variant of the problem where a hard upper bound d on the total distance is given as input, and the size of S^* is to be maximized. The approximation schemes are in fact so simple that our results are best viewed as a performance guarantee on natural heuristics for the problem when the parameters of the heuristic are chosen appropriately. - 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 Abstract We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-size "target set" such that all vertices of the graph get activated. Activation is a dynamic process. First, only the vertices in the target set are activated. Then, a vertex becomes activated if the number of its activated neighbors exceeds its threshold, and so on. TSS models the spread of information and influence in networks. 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.

 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.

 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.

 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.

 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 21August 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.

 19June Jesper Nederlof Möbius inversion 2 12June Jesper Nederlof Möbius inversion 5June Daniel Meister Chordal digraphs 29May Mostofa Ali Patwary A Scalable Parallel Union-Find Algorithm for Distributed Memory Computers 22May Saket Saurabh 3k-Vertex Kernel for Maximum Internal Spanning Tree 15May Venkatesh Raman Polynomial Kernel for Dominating Set on Graphs of Bounded Degeneracy 8May Dieter Kratsch Convex Recoloring Revisited 24April Andrzej Proskurowski Modeling computer/communication networks 17April Daniel Lokshtanov Hypergraph Max-Cut Meets Hypergraph Spanning Tree 3April Holger Dell Sparsification Lower Bounds 27March Isolde Adler The homomorphism problem for structures 20March Binh-Minh Bui-Xuan Need-For-Speed (on the track of an optimal rankwidth decomposition: pros and cons) 6March Pınar Heggernes A guided tour to İstanbul 27February Saket Saurabh Kernelization - A Current View Point 20February Petr Golovach Guarding games on graphs 13February Morten Mjelde PhD defence 6February Daniel Lokshtanov Kernel(s) for Problems With no Kernel:  On Out-Trees With Many Leaves 30January Tınaz Ekim Polar graphs 23January Isolde Adler Computing excluded minors 16January Sang-il Oum Maximum number of complete subgraphs in a certain graph 9January 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 revisitedstarts 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 hypergraphs 20 April Mike Fellows Parameterization of complexity is all about structure theory, and howto 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 ColoringAlgorithms 2 February Saket Saurabh Parameterized complexity ofDirected 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, clique, 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 intoStrong 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 exampleusing relational calculus) 4/12  Dieter Kratsch, Univ Jena, Tyskland 11/12 Pinar Heggernes Partitioning a set of functions into correlated subsets

Planar Contraction