Algorithms seminar series

2022

Autumn 2022

In charge of the seminars this semester is Kenneth Langedal

19.08.2022, Pranabendu Misra, Fixed-Parameter Semi-streaming Algorithms

26.08.2022, Ursula Hebert-Johnson, Counting and Sampling Labeled Chordal Graphs in Polynomial Time

02.09.2022, Vaishali Surianarayanan, Dominating set in weakly closed graphs is fixed parameter tractable

09.09.2022, Saket Saurabh, An FPT Approximation Scheme for the Maximum Coverage Problem

16.09.2022, Tuukka Korhonen, Computing Tree Decompositions with Small Independence Number

23.09.2022, Lars Jaffke, Taming graphs with no large creatures and skinny ladders

07.10.2022, Kenneth Langedal, PACE 2022 submission

21.10.2022, Tuukka Korhonen, Improved Parameterized Algorithm and Approximation Scheme for Treewidth

04.11.2022, Tanmay Inamdar, Tight FPT Approximations for Clustering Problems with Outliers

11.11.2022, Petr Golovach, Maximum Matchings in Frameworks

18.11.2022, Tomohiro Koana, The Complexity of Finding Fair Many-to-One Matchings

25.11.2022, Lars Jaffke, XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure

02.12.2022, Pål Grønås Drange, PACE2023 update meeting

09.12.2022, Boris Djalal, Formalisation of a Newton Series Representation of Polynomials

Spring 2022

In charge of the seminars this semester is Farhad Vadiee

21.01.2022, Petr Golovach, Longest cycle above Erdös-Gallai bound.

28.01.2022, Fedor Fomin, Inconsistent Planning: When in doubt, toss a coin.

04.02.2022, Jan Arne Telle, A new Model of Machine Teaching.

11.02.2022, Petr Golovach, Detours in Directed Graphs.

25.02.2022, Tuukka Korhonen, Paths and Cycles of Large Rank in Frameworks.

04.03.2022, Paloma T. Lima, On the parameterized complexity of b-Coloring.

11.03.2022, Michael Ralph Fellows, PC and Some Heresies of Computational Complexity --- Old, Recent and Yet To Be Properly Explored.

18.03.2022, Ricardo Guimarães, Mining EL Bases with Adaptable Role Depth.

25.03.2022, Daniel Lokshtanov, A Quasi-Complete Classification of Classes with Few Minimal Separators.

08.04.2022, Kirill Simonov, Weighted Model Counting with Twin-Width.

22.04.2022, Matthias Mnich, Simple and fast high-multiplicity scheduling, and hints to the påskekrim.

29.04.2022, Clément Dallard, Tree decompositions with bounded independence number and their algorithmic applications.

29.04.2022, Dag Haugland, Bounds and solution methods for minimum broadcast time.

13.05.2022, Benjamin Bergougnoux, A Logic-Based Algorithmic Meta-Theorem for Mim-Width.

20.05.2022, Céline Swennenhuis, A Faster Exponential Time Algorithm for Bin Packing.

27.05.2022, Fahad Panolan, Partial Vertex Cover on Graphs of Bounded Degeneracy.

03.06.2022, Tuukka Korhonen, Grid Induced Minor Theorem for Graphs of Small Degree.

10.06.2022, Tanmay Inamdar, Non-Uniform k-Center and Greedy Clustering.

17.06.2022, Benjamin Bergougnoux, Recognition of Linear and Star Variants of Leaf Powers is in P.

2021

2020

2019

Autumn 2019

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

22. Nov	Benjamin Bergougnoux	Counting minimal transversal in beta-acyclic hypergraph
15. Nov	Paloma Lima	Computational Social Choice, Trial Lecture
08. Nov	Danil Sagunov	One more generalization of the proper coloring problem
25. Oct	Kirill Simonov	Algorithms for graphs and geometric objects, Midway Assessment
18. Oct	Geevarghese Philip	A 2-factor approximation algorithm for Feedback Vertex Set in tournaments
11. Oct	Lars Jaffke	Typical Sequences Revisited - Computing Width Parameters of Graphs
04. Oct	Nello Blaser	Algorithms in topological data analysis
27. Sep	Torstein Strømme	Utilizing motivation: An extended version of the Scientist Grand Prix talk
20. Sep	Paloma Lima	Reducing the domination number of graphs via edge contractions and vertex deletions
06. Sep	Petr Golovach	Parameterized Low-Rank Binary Matrix Approximation
30. Aug	Sayan Bandyapadhyay	On Perturbation Resilience of Non-Uniform k-Center

Spring 2019

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 Erlend Raa Vågset. Any question can be directed to Erlend (dot) Vagset (at) uib (dot) no

14. June	TBA	TBA
07. June	WorKer	---
31. May	William Lochet	Domination in transitive tournaments
24. May	Morten Brun	Density dependent persistent homology
17. May	Constitution Day	---
13. May	Ferdinand Ihringer	A Construction for Cospectral Graphs.
10. May	Pierre Fraigniaud	Distributed Interactive Proofs
26. Apr	Topi Talvitie	Counting Linear Extensions in Practice
23. Apr	Abhisekh Sankaran	Hereditariness in the finite and prefix classes offirst order logic
19. Apr	Easter	---
12. Apr	Uéverton dos Santos Souza	Knot-free Vertex Deletion: A Deadlock Resolution Graph Problem
05. Apr	Christophe Crespelle	On the effectiveness of the incremental approach to minimal chordal edge modification
29. Mar	Benjamin Bergougnoux	Rank-based Approach on Graphs with Structured Neighborhood.
22. Mar	Phan Thi Ha Duong	Interaction over time and fixed-parameter tractable algorithm on(Bi-)sparse split problem of graph.
15. Mar	Winterschool	---
08. Mar	Charis Papadopoulos	Subset Feedback Vertex Set and Related Terminal Set Problems on Graphs of Bounded Independence Number
01. Mar	Prafullkumar Tale	Graph Contraction Problems : Lossy Kernels and FPT algorithms
22. Feb	Fahad Panolan	On the parameterized complexity of approximating dominating set
15. Feb	Alexander S. Kulikov	Collapsing Superstring Conjecture
01. Feb	Arnaud de Mesmay	Hard cutting problems on embedded graphs
25. Jan	Olav Røthe Bakken	Graph Arrangement Problems Parameterized by Neighbourhood Diversity

2018

Autumn 2018

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

2. Nov	Kirill Simonov	Parameterized Complexity of k-Means Clustering
26. Oct	Petr Golovach	On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
19. Oct	Pratibha Choudhary	Tracking Set Problems
12. Oct	Adam Kabela	Toughness and Hamiltonicity and using duality theorems
5. Oct	William Lochet	Entropy compression and hypergraph orientation
28. Sept	R. Vijayaragunathan	Facility location on Planar Graphs with Unreliable Links
21. Sept	Sebastian Berndt	Computation of Treewidth -- Theory and Practice
14. Sept	Pranabendu Misra	A brief note on Single Source Fault Tolerant Reachability
7. Sept	Yijia Chen	Parameterized AC^0 -- some upper and lower bounds
31. Aug	Carl Feghali	Paths between colourings of degenerate graphs

Spring 2018

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

15. Jun	Cèsar Ferri	Semi-Supervised Clustering Algorithms for Grouping Scientific Articles
8. Jun	---	---
1. Jun	Richard Fellows	Computation-Intensive Applications in Embedded System Design
25. May	Christophe Crespelle	Faster and enhanced minimal cograph completion
18. May	Jana Novotná	List 3-Colouring is polynomial for (P3+P4)- and (P2+P5)-free graphs
11. May	Pranabendu Misra	Popular Matching in Roommates Setting is NP-hard
04. May	Eduard Eiben	Lossy Kernels for Connected Dominating Set on Sparse Graphs
27. Apr	---	(Department Gathering)
20. Apr	Mateus de Oliveira Oliveira	Complexity Measures for Permutation Groups
13. Apr	Laurent Bulteau	The Clever Shopper Problem
06. Apr	Danny Hermelin	New lower bounds for the Bicriteria Shortest Path problem
30. Mar	---	(Easter)
23. Mar	---	(Winter School)
16. Mar	Reza Saei	Extremal Graph Theory, Turan and Ramsey Number
09. Mar	Julie Meißner	Uncertainty Exploration for MST and Scheduling
02. Mar	Dušan Knop	A Unifying Framework for Manipulation Problems
23. Feb	Christophe Crespelle	Structures of Complex Networks and of their Dynamics
16. Feb	Eduard Eiben	How to navigate through obstacles?
09. Feb	Marika Ivanova	The shared multicast tree problem: tightening the LP bounds
02. Feb	Tomáš Masařík	Local Dimension of Posets: Lower & Upper Bounds and Removable Theorems
26. Jan	Frederic Dorn	Set-Based vs Procedural Approach --- or how to Optimize the Running Time of an Algorithm without Changing it
19. Jan	Carl Feghali	Polynomial-Time Extensions of Brooks' Theorem

2017

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

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

15. Dec	Daniel Lokshtanov	Beating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth
08. Dec	--	--
01. Dec	Amer Mouawad	A Theory of Change Through the Lens of Reconfiguration
24. Nov	Bengt Aspvall	Analyzing QuickSelect in a Class Room Setting
17. Nov	Akanksha Agrawal	Graph Modification Problems: Beyond the Known Boundaries (PhD Defense)
10. Nov	Athanasios Konstantinidis	Strong Triadic Closure in Graph Classes
03. Nov	Dusan Knop	Combinatorial n-fold Integer Programming and Applications
27. Oct	Steven Chaplick	Constrained Recognition Problems on Geometric Graph Classes
20. Oct	Krithika Ramaswamy	The Parameterized Complexity of Cycle Packing: Indifference is not an Issue
13. Oct	Fahad Panolan	A Lower bound on Integer Programming
06. Oct	Chhaya Dhingra	On the Convergence of Randomized Label Propagation
29. Sept	Mohsen Alambardar Meybodi	Problems in Dominations and t-spanner graphs
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

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

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 >

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

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

Algorithms seminar series

Main content

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007