Algorithms seminar series

Seminaret bygger på INF234 og INF334, 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.

Main content


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.



Autumn 2021

In charge of the seminars this semester is Emmanuel Arrighi

20.08.21, Fedor Fomin, Paths, Cycles and Beyond

27.08.21, Daniel Lokshtanov, A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane

03.09.21, Svein Høgemo, On Dasgupta's Clustering Objective and its Relation to Other Graph Parameters

10.09.21, Tuukka Korhonen, Lower Bounds on Dynamic Programming for Maximum Weight Independent Set

17.09.21, Giannos Stamoulis, Block Elimination Distance

24.09.21, Emmanuel Arrighi, Order Reconfiguration under Width Constraints

01.10.21, Henning Fernau, Some Parameterized Complexity Results of Natural Combinatorial Problems in Automata Theory and Algebra

06.10.21, Petra Wolf, The Game of Cops and Robbers on Edge Periodic Temporal Graphs

15.10.21, Johannes Langguth, ML Accelerator Hardware: A General Model for Future Parallel Computation?

22.10.21, Emmanuel Arrighi, Order-Related Problems Parameterized by Width

29.10.21, Erlend Vagset, "Finding holes" or "The parameterized complexity of homology localization"

05.11.21, Farhad Vadiee, Dynamic Programming Refutations (PART I)

12.11.21, Srinivas Satti, Succinct representations for graph classes

Spring 2021

In charge of the seminars this semester is Fedor Fomin

Jan 15 Tanmay Inamdar Title: FPT Approximations for Constrained Sum-of-Radii Clustering

Jan 22 Benjamin Bergougnoux Linear Leaf Power Recognition is in P

Jan 29 Saket Saurabh An FPT Algorithm for Elimination Distance to Bounded Degree Graphs

Feb 5 Petr Golovach: Parameterized Complexity of Directed Spanner Problems

Feb 12 Paloma Lima Reducing graph transversals via edge contractions

Feb 19 William Lochet EPTAS for k-means Clustering of Affine Subspaces

March 5 Mateus De Oliveira Oliveira From Dynamic Programming to Automated Theorem Proving

March 19 Nidhi Purohit Parameterized Complexity of Categorical Clustering with Size Constraints


Autumn 2020 (heavy covid restrictions)

02.10.20, Emmanuel Arrighi, Graph Minors 13: The Disjoint Paths Problem

09.10.20, Benjamin Bergougnoux, Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width

16.10.20, Svein Høgemo, Hierarchical Clustering of Unweighted Graphs

Spring 2020

In charge of the seminars this semester is Svein Høgemo

January 31st Lars Jaffke, b-Coloring.

Feb 7 Jan Dreier Counting problems in sparse graphs.

Feb 14 Mateus de Oliveira Oliveira On the Width of Regular Classes of Finite Structures

Feb 21 Stefan Woltran Computational Argumentation -- Formal Models and Complexity Results

Feb 28 Olga Tveretina On the Reachability Problem for Low Dimensional Hybrid Automata

April 3 Fedor Fomin Subexponential parameterized algorithms on almost chordal graphs

April 17 Saket Saurabh Title: On the Complexity of Singly Connected Vertex Deletion

April 24 Mike Fellows Title “Some new results on 'the ultimate fpt classification tool' and work in progress"

May 8 Speaker: Sayan Bandyapadhyay Title: Improved Bounds for Metric Capacitated Covering Problems

May 15 Petr Golovach: Kernelization of Witney Switches

May 22 Speaker: Paloma Lima Title: Rainbow vertex coloring on graph classes

May 29 Speaker: William Lochet Title: Packing and covering balls in graphs excluding a minor


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. NovBenjamin BergougnouxCounting minimal transversal in beta-acyclic hypergraph
15. NovPaloma LimaComputational Social Choice, Trial Lecture
08. NovDanil SagunovOne more generalization of the proper coloring problem
25. OctKirill SimonovAlgorithms for graphs and geometric objects, Midway Assessment
18. OctGeevarghese PhilipA 2-factor approximation algorithm for Feedback Vertex Set in tournaments
11. OctLars JaffkeTypical Sequences Revisited - Computing Width Parameters of Graphs
04. OctNello BlaserAlgorithms in topological data analysis
27. SepTorstein StrømmeUtilizing motivation: An extended version of the Scientist Grand Prix talk
20. SepPaloma LimaReducing the domination number of graphs via edge contractions and vertex deletions
06. SepPetr GolovachParameterized  Low-Rank Binary Matrix Approximation
30. AugSayan BandyapadhyayOn 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. JuneTBATBA
07. JuneWorKer---
31. MayWilliam LochetDomination in transitive tournaments
24. MayMorten BrunDensity dependent persistent homology
17. MayConstitution Day---
13. MayFerdinand Ihringer

A Construction for Cospectral Graphs.

10. MayPierre FraigniaudDistributed Interactive Proofs
26. AprTopi TalvitieCounting Linear Extensions in Practice
23. AprAbhisekh SankaranHereditariness in the finite and prefix classes offirst order logic
19. AprEaster---
12. AprUéverton dos Santos SouzaKnot-free Vertex Deletion: A Deadlock Resolution Graph Problem
05. AprChristophe CrespelleOn the effectiveness of the incremental approach to minimal chordal edge modification
29. MarBenjamin BergougnouxRank-based Approach on Graphs with Structured Neighborhood.
22. MarPhan Thi Ha DuongInteraction over time and fixed-parameter tractable algorithm on(Bi-)sparse split problem of graph.
15. MarWinterschool---
08. MarCharis PapadopoulosSubset Feedback Vertex Set and Related Terminal Set Problems on Graphs of Bounded Independence Number
01. MarPrafullkumar TaleGraph Contraction Problems : Lossy Kernels and FPT algorithms
22. FebFahad PanolanOn the parameterized complexity of approximating dominating set
15. FebAlexander S. KulikovCollapsing Superstring Conjecture
01. FebArnaud de MesmayHard cutting problems on embedded graphs
25. JanOlav Røthe BakkenGraph Arrangement Problems Parameterized by Neighbourhood Diversity


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. NovKirill SimonovParameterized Complexity of k-Means Clustering
26. OctPetr GolovachOn the Parameterized Complexity of Graph Modification to First-Order Logic Properties
19. OctPratibha ChoudharyTracking Set Problems
12. OctAdam KabelaToughness and Hamiltonicity and using duality theorems
5. OctWilliam LochetEntropy compression and hypergraph orientation
28. SeptR. VijayaragunathanFacility location on Planar Graphs with Unreliable Links
21. SeptSebastian BerndtComputation of Treewidth -- Theory and Practice
14. SeptPranabendu MisraA brief note on Single Source Fault Tolerant Reachability
7. SeptYijia ChenParameterized AC^0 -- some upper and lower bounds
31. AugCarl FeghaliPaths 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. JunCèsar FerriSemi-Supervised Clustering Algorithms for Grouping Scientific Articles
8. Jun------
1. JunRichard FellowsComputation-Intensive Applications in Embedded System Design
25. MayChristophe CrespelleFaster and enhanced minimal cograph completion
18. MayJana NovotnáList 3-Colouring is polynomial for (P3+P4)- and (P2+P5)-free graphs
11. MayPranabendu MisraPopular Matching in Roommates Setting is NP-hard
04. MayEduard EibenLossy Kernels for Connected Dominating Set on Sparse Graphs
27. Apr---(Department Gathering)
20. AprMateus de Oliveira OliveiraComplexity Measures for Permutation Groups
13. AprLaurent BulteauThe Clever Shopper Problem
06. AprDanny HermelinNew lower bounds for the Bicriteria Shortest Path problem
30. Mar---(Easter)
23. Mar---(Winter School)
16. MarReza SaeiExtremal Graph Theory, Turan and Ramsey Number
09. MarJulie MeißnerUncertainty Exploration for MST and Scheduling
02. MarDušan KnopA Unifying Framework for Manipulation Problems
23. FebChristophe Crespelle Structures of Complex Networks and of their Dynamics
16. FebEduard EibenHow to navigate through obstacles?
09. FebMarika IvanovaThe shared multicast tree problem: tightening the LP bounds
02. FebTomáš MasaříkLocal Dimension of Posets: Lower & Upper Bounds and Removable Theorems
26. JanFrederic DornSet-Based vs Procedural Approach --- or how to Optimize the Running Time of an Algorithm without Changing it
19. JanCarl FeghaliPolynomial-Time Extensions of Brooks' Theorem


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.


15. DecDaniel LokshtanovBeating Brute Force for (Quantified) Satisfiability of Circuits of Bounded Treewidth
08. Dec----
01. DecAmer MouawadA Theory of Change Through the Lens of Reconfiguration
24. NovBengt AspvallAnalyzing QuickSelect in a Class Room Setting
17. NovAkanksha AgrawalGraph Modification Problems: Beyond the Known Boundaries (PhD Defense)
10. NovAthanasios KonstantinidisStrong Triadic Closure in Graph Classes
03. NovDusan KnopCombinatorial n-fold Integer Programming and Applications
27. OctSteven ChaplickConstrained Recognition Problems on Geometric Graph Classes
20. OctKrithika RamaswamyThe Parameterized Complexity of Cycle Packing: Indifference is not an Issue
13. OctFahad PanolanA Lower bound on Integer Programming
06. OctChhaya DhingraOn the Convergence of Randomized Label Propagation
29. SeptMohsen Alambardar MeybodiProblems in Dominations and t-spanner graphs
22. SeptSebastian SiebertzA tutorial on uniform quasi-wideness
15. SeptMateus OliveiraGround Reachability and Joinability in Linear Term Rewriting Systems are Fixed Parameter Tractable with Respect to Depth
08. SeptRoohani SharmaSub-exponential Fixed-Parameter Tractable Algorithm for Directed Feedback Arc Set in a Special Class of Digraphs
01. SeptLars JaffkePolynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width
25. AugPranabendu MisraBipartite Perfect Matching is in quasi-NC
18. AugIvan MihajlinIrreducibility in fine-grained complexity


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. DecMarija SlavkovikJudgment aggregation and its complexity
25. NovPranabendu MisraLossy Kernels for Graph Contraction Problems
18. NovPedro MontealegreParameterized algorithms via minimal triangulations and potential maximal cliques
11. NovChristophe CrespelleLinearity is Strictly More Powerful than Contiguity for Encoding Graphs
04. NovSanjukta RoyStable Matching Games: Manipulation via Subgraph Isomorphism

28. Oct

Amer E. MouawadPacking Cycles Faster Than Erdős-Pósa

21. Oct

Marcin WrochnaAlgorithms 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 OliveiraTree-Zig-Zag Number of a digraph - Applications and Open Problems

23. Sept

Md. NaimCommunity Detection on GPU

16. Sept

PrafullKumar P TaleDynamic Parameterized Problems
02. SeptDiptapriyo 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 10Fichte/Charwat 
Jun 8
Junjie Ye 
Jun 2 (Thur)  
May 27O-joung KwonA single-exponential fixed parameter algorithm for Distance-Hereditary Vertex Deletion
May 20Daniel LokshtanovLower bounds for approximation schemes for Closest String
May 13Sushmita GuptaStable matching games: Manipulation via graph connectivity
May 6 Cancelled
Apr 29 Department gathering
Apr 22Jan Arne Telle 
Apr 15Edvin BerglinApplications of incidence in point covering problems
Apr 8Gunnar FløystadThe interplay between graphs, simplicial complexes and ring theory
Apr 1Mithilesh KumarComponent Order Connectivity
Mar 25 Easter Vacation
Mar 17 (Thur @ 14:15)Mateus de Oliveira OliveiraAn Algorithmic Metatheorem for Graph Completion Problems
Mar 11Saket SaurabhCommunication Complexity of Pairs of Graph Families with Applications
Mar 4M. S. RamanujanA Linear Time Parameterized Algorithm for Feedback Vertex Set on Directed Graphs
Feb 26Fahad PanolanEditing to Connected f-Degree Graph
Feb 19Michal WalickiKernels of Infinite Digraphs
Feb 12Petr GolovachParameterized Complexity of Secluded Connectivity Problems
Feb 5
Daniel LokshtanovBelow the Trivial Upper Bound for the Number of Minimal Connected Dominating Sets
Jan 29 Cancelled
Jan 22Erik ParmannCase Studies in Constructive Mathematics (PhD defence)
Jan 15Damien ProtFrom classical (for me) to classical (for you) tools in scheduling theory
Jan 8Tarek R. BesoldLike a Cognitive Walk in the Computational Park: Of  Atom Models and Foldable Toothbrushes
Jan 6Kitty MeeksWhen can an FPT decision algorithm be used to count?


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. DecMagnus  WahlstromA combinatorial condition for FPT LP-branching
04. DecAkanksha Agrawal 
27. Nov Daniel LokshtanovParameterized Integer Quadratic Programming: Variables and Coefficients
20. NovAmer MouawadSimultaneous Feedback Vertex Set: A Parameterized Perspective
13. NovJan Arne TelleRecognizability 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 DrangeEmpirical hardness models: focusing on instance distributions representative of practical applications rather than worst-case.

19. Oct

Faisal Abu KhzamThe 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 MajumdarKernels for Structural Parameterizations of Vertex Cover - Case of Small Degree Modulators

30. Sept

Meriav ZehaviNon-Standard Usage of the Method of Bounded Search Trees

25. Sept

Torstein Strømme"Structural" kernelization for Vertex Cover.
18. Sept No Seminar
11. SeptJan 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.JunePranabendu MisraDeterministic Truncation of Linear Matroids
12.JuneSudeshna KolayParameterized Algorithms for deleting to (r,l)-graphs
05.June Marcin Wrochna Recoloring graph homomorphisms using basic topology
29. MayReza SaeiPhD defence
22. MayProf. 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. AprilReza Saei Graph spectra
17. AprilJakub Gajarský MSO Logic on Trees of Bounded Height
10. AprilProf.  Mike Fellow FPT is Extremal Gradients: A Partial Preview of an ERC Proposal
03. April  No seminar (Holiday)
27. MarchMd. Naim GPU architecture and Graph Algorithm
20. MarchDieter Kratsch Exact Exponential Algorithms
13. MarchDaniel Lokshtanov Subset Feed Back Vertex Set in O(25.6^k(|V(G)|+|E(G)|)) time
06. MarchPetr Golovach How to Hunt an Invisible Rabbit on a Graph
27. FebruaryFelix Reidl Structural sparsity in the real world
20. FebruaryMarkus S. Dregi On the Computational Complexity of Vertex Integrity and Component Order Connectivity
13. FebruaryRémy Belmonte   Induced Minor Free Graphs: Isomorphism and Clique-width  
06. FebruaryAkanksha Agrawal Vertex Cover on Delaunay Graphs
30. JanuaryM S Ramanujan A parameterized complexity dichotomy for Boolean QCSP Deletion
23. JanuaryPetr Golovach Editing to Eulerian Graphs
16. JanuaryPål G. Drange Editing to Threshold Graphs




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.decChristophe CrespelleA Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph With Regard to the Cartesian Product
05.dec Daniel LokshtanovSurprise !!
28.nov Saket SaurabhSolving Multicut faster than 2^n
21.novKristina VuskovicProof of the Confort-Rao Conjecture for linear balanced matrices
14.novIsolde AdlerPAC learning of FO definable concepts & nowhere dense graph classes
07.nov No Seminar
31.octSebastian OrdyniakBackdoors into Heterogeneous Classes of SAT and CSP
24.oct Open Problems Session
17.oct No Seminar
10.oct Sigve SætherBetween Treewidth and Clique-Width
03.octMithilesh KumarFaster Feedback Vertex Set in Tournaments
26.sepAmer MouawadReconfiguration problems: Structure and tractability
19.sepFahad P.Faster FPT Algorithm for Eulerian Edge Deletion
12.sepAshutosh RaiOn the kernelization complexity of String Problems
05.sepReza SaeiReconfiguration graphs and problems
29. augSandeep  R.B.On Polynomial Kernelization of H-free Edge Deletion
22. augNANo Seminar
15. augBlair SullivanBringing 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. JuniNo seminar 
20. JuniMarkus DregiParameterized Complexity of Bandwidth on Trees.
13. JuniMichael R. FellowsParameterized Complexity AND Incremental Computing: some good news
6. JuniDaniel LokshtanovFixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth
30. MayNo seminar 
23. MayAlexey Stepanov Applications of TSP in real life
16. May Fabrizio Grandoni Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
9. MayBart Jansen 
2. May No seminar 
25. AprilRump Session 
18. April Easter 
11. April Marcin Pilipczuk Online and dynamic algorithms for the Steiner tree problem.
4. AprilM S RamanujanParameterized Algorithms to Preserve Connectivity.
28. MarchSadia SharminGraph Partitioning
21. MarchWinter school 
14. March

Fernando S Villaamil

Computing Treedepth

7. MarchErik Jan van Leeuwen

Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs

28. FebruaryPål Grønås DrangeSubexponential Parameterized Complexity of Completion Problems
21. February

Peter Bro Miltersen

Real algebraic geometry in computational game theory - a consumer's perspective

14. FebruarySigve H SætherDomination Set parameterised by Clique-width
7. FebruaryReza SaeiFinding Disjoint Paths in Split Graphs
31. January

Ariel Gabizon

The r-simple k-path problem
24. JanuaryPinar HeggernesEnumeration in Graph Classes
17. JanuaryMichał PilipczukMinimum Bisection is FPT
10. JanuaryManu BasavarajuPartially Polynomial Kernels for SetCover and TestCover




Høstsemesteret 2013

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




Vårsemesteret 2013

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

14 JuneMichał PilipczukA polynomial kernel for Planar Steiner Tree parameterized by the size of the tree
7 JuneDániel MarxCSPs and fixed-parameter tractability
31 MayFredrik ManneEfficient Sequential and Multicore Weighted Matching Algorithms
24 MayOndřej SuchýOn Explaining Integer Vectors by Few Homogenous Segments
17 MayNorwegian Constitution Day
10 MayMamadou KantéOn the linear rank-width and linear clique-width of Trees
3 MaySadia SharminEfficient Counting of Maximal Independent Sets in Sparse Graphs
26 AprilArvid LundervoldThe role of graph theory and network analysis in quantitative neuroimaging
19 AprilEmilio CoppaFrom asymptotics to performance profiling (and back)
12 April< No seminar >
5 AprilM. S. RamanujanBackdoors to Satisfiability via q-horn formulas
29 MarchEaster holiday
22 MarchJean-François CouturierA tight bound on the number of minimal dominating sets in split graph
15 MarchDimitrios M. ThilikosPolynomial gap extensions of the Erdős-Pósa theorem
8 MarchHenning FernauA multivariate analysis of pattern language problems
1 MarchDaniel MeisterRecent developments in clique-width computation
22 FebruaryWinter School 2013
15 FebruaryRémy BelmonteGraph rewriting
8 FebruaryYixin CaoInterval Deletion is Fixed-Parameter Tractable
1 FebruaryRémy BelmonteInduced Immersions
25 JanuarySven SimonsenThe complexity of finding arc-disjoint spanning trees and branchings in digraphs. FPT approach.
18 JanuaryDaniel LokshtanovNear-Tight Bounds for Cross-Validation via Loss Stability
11 January< No seminar >




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 DecemberArchontia GiannopoulouLifo-search on (Di)graphs
7 DecemberPinar HeggernesThe maximum number of feedback vertex sets in chordal graphs and cographs
5 December*Hans BodlaenderConnectivity problems on graphs of small treewidth
30 NovemberHans BodlaenderPreprocessing and kernelization for Treewidth and Pathwidth
23 NovemberFedor V FominSubexponential Parametrized Algorithm for Cluster Editing
16 NovemberReza SaeidinvarRamsey Numbers for Line Graphs and Perfect Graphs
9 NovemberErik Jan van LeeuwenParameterized Complexity of Induced H-Matching on Claw-Free Graphs
2 NovemberJanne KorhonenCounting in Halves and Fast Monotone Summation over Disjoint Sets
26 OctoberPim van 't HofOn the parameterized complexity of finding separators with non-hereditary properties
19 OctoberIvan BliznetsA new algorithm for parametrized MAX-SAT
12 OctoberDaniel LokshtanovPolynomial Kernel for Planar F-Deletions
5 OctoberIgnasi SauParameterized domination in circle graphs
28 SeptemberMichał PilipczukRandomized contractions
21 SeptemberYngve VillangerSearching for better fill-in
14 SeptemberMartin VatshelleThe Point-Set Embeddability Problem for Plane Graphs
7 SeptemberFrederic DornShort-term hydro scheduling from the algorithmic perspective
3 September*Bruce ReedCatching a Drunk Miscreant
31 AugustHenning FernauSaving on Phases: Parameterized Approximation for Total Vertex Cover
24 AugustRajesh ChitnisDirected Multiway Cut is FPT
17 AugustJan Arne TelleFPT 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 MayPeter GolovachInduced Disjoint Paths in AT-free Graphs
8 JuneMartin VatshelleLower bounds on treewidth for practical computing (trial lecture)
1 June Mini-school on Width-Minors-Matroids
25 MayArash RafieyOrdering without bad patterns
11 MayRémy BelmonteOpen problems session
27 AprilMichał PilipczukOn group feedback vertex set parameterized by the size of the cutset

30 March

Igor SemaevFrom Jacob Bernoulli to Modern Cryptography
23 MarchBengt AspvallSorting Algorithms As Special Cases Of A Priority Queue Sort
16 MarchPim van 't HofObtaining a Bipartite Graph by Contracting Few Edges
9 MarchArash RafieyHomomorphism Problem and Approximation
2 MarchMichał PilipczukOpen problems session
24 FebruaryFinse

10th Annual Winter School in Algorithms, Graph Theory, and Combinatorics

17 FebruaryPål Grønås DrangeA randomized polynomial kernel for Odd Cycle Transversal
10 FebruarySigve H. SætherBroadcast domination on block graphs
3 FebruaryMartin MilanicOn the (in-)approximability and exact algorithms for vector domination and related problems in graphs
20 JanuaryJean-Francois CouturierMaximum number of minimal dominating sets in graph classes
13 JanuaryErik Jan van LeeuwenAlgorithms for firefighting
6 JanuaryDaniel LokshtanovFaster Vertex Cover above LP




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 DecemberRémy BelmonteFinding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
9 December, 10.15, Large Auditorium!!Jesper NederlofSpace and Time Efficient Structural Improvements of Dynamic Programming Algorithms (PhD dissertation)
2 DecemberMichał PilipczukSolving 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 NederlofProperty testing (Trial lecture)
18 NovemberHenning FernauParameterized 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 NovemberDaniel PaulusmaLift 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 NovemberRuben van der ZwaanPreemptive 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 OctoberBart JansenPreprocessing 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 OctoberPetteri KaskiFast 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 OctoberNo Seminar
7 OctoberMichał 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 SeptemberFedor FominLinear kernels for dominating set on H-minor-free graphs
23 SeptemberRamanujan Maadapuzhi SridharanA 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 SaurabhSurprise 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 AugustAndré 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 JuneReza SaeiSome Topics on Domination
10 June (Minicourse by Patrice Ossona de Mendez)
27 MaySerge GaspersKernels for Global Constraints
20 May (Treewidth Workshop)
13 MayPetr GolovachComputing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
29 AprilPim van 't HofContracting Graphs to Paths and Trees 
22 April (Easter Break)
15 AprilDaniel MeisterInduced Subgraph Isomorphism on Two Classes of Perfect Graphs
8 AprilErik Jan van Leeuwen 

PTAS for Weighted Set Cover on Unit Squares

1 AprilJohannes LangguthSequential and Parallel Algorithms for Bipartite Matching
25 MarchMarek CyganThe Stubborn Problem is Stubborn No More
18 MarchYuri RabinovichOn Complexity of the Sub-Pattern Problem
11 MarchFredrik ManneEfficient Self-Stabilizing Graph Searching in Trees
4 MarchJan Arne TelleLocally Constrained H-Homomorphism on Graphs of Logarithmic Boolean-Width
25 February    (Winter School)
18 FebruarySven KöhlerFault-Containing Self-Stabilization in Asynchronous Systems with Constant Fault-Gap
11 FebruaryDimitrios ThilikosDeciding More Containment Relations in Embedded Graphs in FPT Time
4 FebruaryBengt AspvallUtforske Matematikk fra IKT (Uten Bruk av Datamaskin) - Departmental seminar, 13:15-15:00, Lille Auditorium, SV-bygget 
28 JanuaryThomas ÅgotnesNormative State Transition Systems: Logic, Games and Complexity
7 JanuaryBart JansenVertex Cover Kernelization Revisited: Upper and Lower Bounds for a Refined Parameter




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 DecemberJan Arne TelleSocial Networks
26 NovemberLisa SchreiberThe Unbounded Knapsack Problem and the Generalized Cordel Property
19 NovemberGeevarghese Philipt-Total Vertex/Edge Cover: Fixed Parameter Tractability and Kernelization Complexity
5 NovemberFran RosamondOn the Complexity of Some Constraint Satisfaction Problems with Global Constraints and Convexity
29 OctoberDanny HermelinMinimum Vertex Cover in Rectangle Graphs
15 OctoberBinh-Minh Bui-XuanRecipe for computing generalisations of modular decomposition
8 OctoberNeeldhara MisraConnected Dominating Set and Short Cycles
1 OctoberMike FellowsWhy vote?
24 SeptemberFrederic DornFast Minor Testing in Planar Graphs
17 SeptemberMartin VatshelleFaster Algorithms on Branch and Clique Decompositions
10 SeptemberSaket SaurabhParameterized Problems that have Slightly Superexponential Time Algorithms
3 SeptemberFrank KammerApproximate Tree Decompositions of Planar Graphs in Linear Time
27 AugustFrank KammerDisjoint Paths on Chordal Graphs
20 AugustDaniel LokshtanovClustering 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 JuneYahav NussbaumMaximum Flow in Directed Planar Graphs with Vertex Capacities
10 JunePinar HeggernesGeneralized graph clustering: recognizing (p,q)-cluster graphs
3 JuneRémy BelmonteOn classes of graphs with logarithmic boolean-width
27 MayDieter KratschColorings with few colors
6 MayMichel HabibOn the computation of 2-join
29 AprilErik Jan van LeeuwenParameterized approximability: EPTAS and beyond
8 AprilDaniel MeisterAbout the existence of good digraph width measures
25 MarchMostofa PatwaryExperiments on Union-Find Algorithms for the Disjoint-Set Data Structure
18 MarchPetr GolovachCops and Robber Game Without Recharging
11 MarchPierre FraigniaudCompact Ancestry Schemes and Small Universal Posets
25 February(Winter School) 
18 FebruaryJohannes LangguthA parallel algorithm for bipartite matching
11 FebruaryJesper NederlofSaving Space by Algebraization 2
4 FebruaryDaniel LokshtanovKnown Bounded Treewidth Algorithms are (Probably) Optimal
28 JanuaryMamadou KantéRank-width of edge-colored graphs
21 JanuaryNicolas BourgeoisApproximating with moderately exponential algorithms
15 JanuaryFrederic DornA faster FPT-algorithm for Planar Subgraph Isomorphism



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 DecemberJean Blair
Discovering Open Graph Theoretic Problems Motivated by Network Science
4 DecemberJohan van RooijExact Algorithms for Edge Domination
27 NovemberPim van 't HofComputing Role Assignments of Chordal Graphs
20 NovemberDaniel LokshtanovSaving Space By Algebraization
6 NovemberPinar HeggernesLinear clique-width of some proper interval graphs
30 October Rodica MihaiEdge search number of cographs in linear time
23 October 25th anniversary of Department of informatics
16 October GROW 2009
9 OctoberMichaël RaoLast Cases of Dejean's Conjecture
2 OctoberFedor V. FominLocal Search: Is brute-force avoidable?
25 SeptemberAbhijin AdigaLower Bounds for Boxicity
18 SeptemberJean BlairAn Efficient Self-stabilizing Distance-2 Coloring Algorithm
4 SeptemberPaul BonsmaFinding fullerene patches in polynomial time
28 AugustSourav ChakrabortyMarket Equilibrium with Transaction Costs
Yuri RabinovichOn 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).


Jesper NederlofMöbius inversion 2
Jesper NederlofMöbius inversion
Daniel MeisterChordal digraphs
Mostofa Ali PatwaryA Scalable Parallel Union-Find Algorithm for Distributed Memory Computers
Saket Saurabh3k-Vertex Kernel for Maximum Internal Spanning Tree
Venkatesh RamanPolynomial Kernel for Dominating Set on Graphs of Bounded Degeneracy
Dieter KratschConvex Recoloring Revisited
Andrzej ProskurowskiModeling computer/communication networks
Daniel LokshtanovHypergraph Max-Cut Meets Hypergraph Spanning Tree
Holger DellSparsification Lower Bounds
Isolde AdlerThe homomorphism problem for structures
Binh-Minh Bui-XuanNeed-For-Speed (on the track of an optimal rankwidth decomposition: pros and cons)
Pınar HeggernesA guided tour to İstanbul
Saket SaurabhKernelization - A Current View Point
Petr GolovachGuarding games on graphs
Morten MjeldePhD defence
Daniel LokshtanovKernel(s) for Problems With no Kernel:  On Out-Trees With Many Leaves
Tınaz EkimPolar graphs
Isolde AdlerComputing excluded minors
Sang-il OumMaximum number of complete subgraphs in a certain graph
Yngve VillangerFaster parameterized algorithms for Minimum Fill-in


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 DecemberJesper NederlofInclusion-exclusion for hard problems
28 NovemberIoan Todinca 
21 NovemberRuben van der ZwaanVertex ranking
14 NovemberHaiko MüllerOn a Disparity Between Relative Cliquewidth and Relative NLC-width
7 NovemberBinh-Minh Bui-XuanOn speeding up divide-and-conquer algorithms: making faster unifications or
 doing less conquests?
31 OctoberMatthias MnichComputing a Maximum Agreement Supertree
17 OctoberFederico ManciniClustering with partial information
10 OctoberJan Arne TelleThe Bergen Graph Parameter Project, a proposal for discussion
3 OctoberMichal WalickiKernels of digraphs
26 SeptemberDaniel LokshtanovGraph Layout Problems Parameterized by Vertex Cover
19 SeptemberMichel HabibMinimal separators and maximal cliques in chordal graphs revisited

starts 11:00 in room 3137
12 SeptemberPetr GolovachA PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
5 SeptemberSerge GaspersIterative Compression and Exact Algorithms
22 AugustFederico ManciniAlgorithms 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 FebruaryBinh-Minh Bui-XuanTree-representation of set families and graph decompositions
15 FebruaryPetr GolovachGeneralized domination in degenerate graphs: ambivalence and complexity
22 FebruarySerge GaspersCleaning and Protecting a Graph
29 FebruaryMorten MjeldeTemporal Partition in Sensor Networks.
7 MarchJohannes LangguthMarket Equilibria
14 MarchJoanna BauerDissertation
28 MarchMichael FellowsCorrelation Clustering, Graph Separation, and Removing Necklaces: A Tale of Equivalent Open Problems
4 AprilMikko KoivistoExponential-time algorithms for Bayesian networks
11 AprilDaniel LokshtanovCutwidth of split graphs, threshold graphs, and proper interval graphs
18 AprilGregori SorkinFaster solving, counting, and sampling
25 AprilSaket SaurabhFinding sub graphs whose matching number equals its minimum vertex cover number
9 MayPetteri KaskiDeletion--contraction invariants and fast subset convolution
23 MayMarc BezemShortest paths in hypergraphs
30 MayFrederic DornAn FPT Algorithm for Directed Spanning k-leaf
6 JuneYngve VillangerComputing treewidth with a help of firefighters
13 JuneJan Arne TelleH-join graphs and rankwidth
20 JuneLene Monrad FavrholdtComparing First-Fit and Next-Fit for Online Edge Coloring
27 JuneSushmita GuptaFeedback Art set problem in bipartite tournaments


Høstsemesteret 2007

In charge of the seminars is Daniel Lokshtanov.
-- Every Friday we have Algorithms seminar in Room 2143 at 12:30.

30 NovemberPetr GolovachOn tractability of Cops and Robbers game
14 SeptemberFrederic DornDissertation
7 SeptemberFedor FominParameterized subexponential algorithms 
31 AugustYngve VillangerImproved 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 JuneFeodor DraganDistance and Routing Labeling Schemes in Graphs with Applications
8 JuneR. Sritharan4-leaf powers: structure and recognition
1 JuneYngve Villangerk-interval completions
1 JuneMoritz MuellerParameterized Analogues of the Valiant-
Vazirani Lemma
25 MayDanny HermelinLower bounds for kernelization
18 MayPetr GolovachComputational complexity of generalized domination for chordal graphs
11 MayQin XinFaster treasure hunts and better strongly universal exploration sequencestd>
4 May-Research school
27 AprilElena LosievskajaApproximation algorithms for the Maximum Independent set problem in hypergr
20 AprilMike FellowsParameterization of complexity is all about structure theory, and how
to use it
13 AprilDimitrios M. ThilikosGraph Searching in a Crime Wave
30 MarchRodica MihaiMixed search number and linear-width of interval and split graphs
23 MarchCharis PapadopulosSingle-edge monotonic sequences of graphs
16 MarchMathieu LiedloffAn exact algorithm for the minimum dominating clique problem
9 MarchMorten MjeldeSelf-stabilizing matching
2 March