Informatyka Teoretyczna

prof. dr hab. Paweł M. Idziak

środa 16:15 - 18:00, sala 0174

This is our main seminar. We study problems in graph theory, partial ordered sets, online algorithms, computational complexity. This is also the place where we present our most recent results.

03.04.2024 16:15
David Conlon
California Institute of Technology
Additive combinatorics without (much) addition

We describe recent progress on a number of related themes in additive combinatorics, including estimating the clique number of random Cayley graphs and showing that there are Cayley graphs which are good Ramsey graphs. Surprisingly, the proofs of these results rely only weakly on the group structure and the proofs are mainly about the structure of properly edge-coloured graphs.

Joint work with Jacob Fox, Huy Tuan Pham and Liana Yepremyan.

10.04.2024 16:15
Jean Cardinal
Université Libre de Bruxelles
A rectangulation is a decomposition of a rectangle into finitely many rectangles

Via natural equivalence relations, rectangulations can be seen as combinatorial objects with a rich structure, with links to lattice congruences, flip graphs, polytopes, lattice paths, Hopf algebras, etc.

I will explain the structure of two equivalence classes: weak rectangulations that preserve rectangle-segment adjacencies, and strong rectangulations that preserve rectangle-rectangle adjacencies.

These equivalences classes are proved to be in correspondence with sets of linear extensions of partial orders on rectangles. This yields a uniform treatment of mappings between permutations and rectangulations, unifying results from earlier contributions. I will also touch upon geometric realizations of the rectangulation polytopes. Just like permutohedra and associahedra encode flip graphs on permutations and triangulations, the skeleta of rectangulation polytopes are flip graphs on rectangulations.

This is joint work with Andrei Asinowski, Stefan Felsner, Éric Fusy, and Vincent Pilaud.

17.04.2024 16:15
TBA
TBA - 2024.04.17
24.04.2024 16:15
Alexander Wolff
Universität Würzburg
TBA - 2024.04.24 - Alexander Wolff
08.05.2024 16:15
TBA
TBA - 2024.05.08
15.05.2024 16:15
Marta Kwiatkowska
University of Oxford
TBA - 2024.05.15 - Marta Kwiatkowska
22.05.2024 16:15
TBA
TBA - 2024.05.22
29.05.2024 16:15
TBA
TBA - 2024.05.29
05.06.2024 16:15
Maria Chudnovsky
Princeton University
TBA - 2024.06.05 - Maria Chudnovsky
12.06.2024 16:15
TBA
TBA - 2024.06.12
02.10.2024 16:15
TBA
TBA - 2024.10.02
09.10.2024 16:15
TBA
TBA - 2024.10.09

Poprzednie referaty

27.03.2024 16:15
Clément Rambaud
Université Côte d'Azur
Inversions in oriented graphs

The inversion of a set X of vertices in an oriented graph consists in reversing the direction of all arcs of the subdigraph induced by X. This generalization of single arc reversal introduced by Belkhechine et al. yields a notion of distance between orientations of a same graph where two orientations are at distance one if and only if there is a set X whose inversion transforms one into the other. First we will discuss the minimum number of inversions required to make an oriented graph acyclic, and in particular a proof of the existence of n-vertex oriented graphs at distance n-o(n) of any acyclic orientation. We also investigate the minimum number of inversions needed to make an oriented graph k-strongly-connected, especially in the case of tournaments. Finally, we show various bounds on the maximum distance between two orientations of a same graph. This gives an undirected graph parameter that we show to be tied to several known parameters, including the star chromatic number and acyclic chromatic number. We also prove that two orientations of a same planar graph are at distance at most 12. Most of these results rely on an algebraic point of view that allows us to use linear algebra over the field with two elements.

This is joint work with Guillaume Aubian, Julien Duron, Frédéric Havet, Florian Horsch, Felix Klingelhoefer, Nicolas Nisse, and Quentin Vermande.

20.03.2024 16:15
Gábor Tardos
Alfréd Rényi Institute of Mathematics
Forbidden acyclic patterns in 0-1 matrices
A zero-one matrix M is said to contain another zero-one matrix A if we can delete some rows and columns of M and replace some 1-entries with 0-entries such that the resulting matrix is A. The extremal function of A, denoted ex(n,A), is the maximum number of 1-entries that an n×n zero-one matrix can have without containing A. The systematic study of this function for various patterns A goes back to the work of Füredi and Hajnal from 1992. The field has many connections to other areas such as classical Turán type extremal graph theory and Davenport-Schinzel theory and has many applications in mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices. Füredi and Hajnal conjectured an O(n·log n) bound for them, while Pach and Tardos conjectured a weaker n·polylog n bound. Pettie refuted the stronger conjecture with an acyclic pattern whose extremal function he showed to be Ω(n·log n · loglog n).
 
In a recent joint work with Seth Pettie we found the extremal function ex(n,Ak) asymptotically for certain simple 2×k acyclic patterns to be Θ(n·(log n/loglog n)k−2) for k>3. This shows that the Pach-Tardos conjecture is tight if true. The conjecture itself is still wide open.
06.03.2024 16:15
Jacob Fox
Stanford University
Structure theorems for intersection patterns of geometric objects

In this talk we discuss Szemerédi-type structure theorems, Ramsey-type theorems, and Turán-type theorems for intersection patterns of geometric objects and their relationships to each other. In particular, we discuss recent such results on intersection graphs of pseudo-segments and an application which gives a new upper bound on the number of edges of a simple topological graph with no k pairwise disjoint edges.

Joint work with János Pach and Andrew Suk.

24.01.2024 16:15
Sergio Cabello
University of Ljubljana and IMFM, Slovenia
Packing d-dimensional balls into a (d+1)-dimensional container

We consider the problems of finding in d+1 dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of d-dimensional unit-radius balls can be packed under translations. We give a constant-factor approximation algorithm for each of these containers. We also show that for n such balls, a container of volume O(n1−1/d) is always sufficient and sometimes necessary.

Joint work with Helmut Alt, Otfried Cheong, Ji-won Park and Nadja Seiferth.

17.01.2024 16:15
Jim Geelen
University of Waterloo
Average plane size

Consider a finite set of distinct points in d-dimensional Euclidean space. A line is said to be spanned if it contains two distinct points from the given set, and a plane is spanned if it contains three non-collinear points from the given set. In 1941, Melchior proved that the average number of given points on a spanned line is bounded above by 3, unless the given points all lie on a single line. We prove that the average number of given points on a spanned plane is bounded above by an absolute constant, unless all of the given points lie on a single plane or they lie on the union of two lines.

This is joint work with Rutger Campbell and Matthew Kroeker.

10.01.2024 16:15
Peter Allen
London School of Economics and Political Science
Universality for degenerate graphs

A graph G is universal for a family of graphs if for each F in  there is a copy of F in G (not necessarily induced, and the copies are not necessarily disjoint).

Alon and Capalbo considered the case that is the family of n-vertex graphs with maximum degree k, and showed that there is a universal graph for this family with O(n2-2/k) edges, which is sharp. Alon asked what the answer is if one replaces 'maximum degree' with 'degeneracy'.

We give a probabilistic construction of a universal graph for the family of n-vertex d-degenerate graphs with Õ(n2-1/d) edges, which is optimal up to the polylog. In this talk, I will describe the construction and give most of the details of the proof of its universality.

This is joint work with Julia Boettcher and Anita Liebenau.

20.12.2023 16:15
Paweł Rzążewski
Warsaw University of Technology
Understanding graphs with no long claws

A classic result of Alekseev asserts that for connected H the MAX INDEPENDENT SET (MIS) problem in H-free graphs in NP-hard unless H is a path or a subdivided claw. Recently we have witnessed some great progress in understanding the complexity of MIS in Pt-free graphs. The situation for forbidden subdivided claws is, however, much less understood.

During the talk we will present some recent advances in understanding the structure of graphs with no long induced claws. We are able to use them to obtain a quasipolynomial-time algorithm for the problem.

13.12.2023 00:00

The 17th workshop on Computational Logic and Applications
06.12.2023 16:15
Paul Bastide
LaBRI, Bordeaux
Skipless chain decompositions and improved poset saturation bounds

We show that given m disjoint chains in the Boolean lattice, we can create m disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer two conjectures about the asymptotics of induced saturation numbers for the antichain, which are defined as follows. For positive integers k and n, a family F of subsets of {1,...,n} is k-antichain saturated if it does not contain an antichain of size k (as induced subposet), but adding any set to F creates an antichain of size k. We use sat*(n,k) to denote the smallest size of such a family. With more work we pinpoint the exact value of sat*(n,k), for all k and sufficiently large n. Previously, exact values for sat*(n,k) were only known for k up to 6.

We also show that for any poset P, its induced saturation number (which is defined similar as for the antichain) grows at most polynomially: sat*(n,P)=O(nc), where c|P|2/4+1.

This is based on joint works with Carla Groenland, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.

29.11.2023 16:15
Matthieu Rosenfeld
LIRMM, Montpellier
A simple counting argument applied to graph colorings

The Lovász Local Lemma is one of the central tools of Erdős' probabilistic method. This rather simple lemma has been applied to SAT formulas, graph colorings, hypergraph coloring, combinatorics on words, geometry, and countless other topics. This Lemma essentially tells that given a set of "bad events", under the right conditions, the probability that no events occur is nonzero. It implies the existence of a coloring or an affection of the variables with the desired properties. There are many versions of the Lovász Local Lemma that apply to different situations. Many related techniques that apply to similar problems have emerged in the last 20 years (entropy compression, cluster expansion, local cut lemma...). Recently, I have introduced a counting argument that belongs to the same family of technique. The main interest of this counting argument is that it is really simple to use and it has already been applied to different problems by a few different authors.

In this presentation, I will present this counting argument. We will apply this technique to one or two simple examples from graph theory to illustrate how it works. I will try to give a broad intuition behind a couple of more involved results that were achieved by different authors with this technique.

22.11.2023 16:15
Gábor Damásdi
Alfréd Rényi Institute of Mathematics
Monochromatic configurations on the circle

In this lecture we will discuss a surprising combinatorial conjecture. For  k≥3 call a k-tuple (d1,d2,...,dk)  with  d1d2≥...≥dk>0  and d1+d2+...+dk=1   a Ramsey k-tuple if the following is true: in every two-colouring of the circle of unit perimeter, there is a monochromatic k-tuple of points in which the distances of cyclically consecutive points, measured along the arcs, are d1,d2,...,dk in some order. By a conjecture of Stromquist, if  di=2k-i/(2k-1),  then d1,d2,...,dk is Ramsey. Using Sat solvers we showed that the conjecture holds for k7. Our main result is a proof of the converse of this conjecture. That is, we show that if (d1,d2,...,dk) is Ramsey, then di=2k-i/(2k-1). We do this by finding connections of the problem to certain questions from number theory about partitioning N into so-called Beatty sequences.

 

15.11.2023 16:15
Piotr Micek
Jagiellonian
Tight bound for the Erdős-Pósa property of tree minors

Let T be a tree on t vertices. We prove that for every positive integer k and every graph G, either G contains k pairwise vertex-disjoint subgraphs each having a T minor, or there exists a set X of at most t(k-1) vertices of G such that  G-X has no T minor. The bound on the size of X is best  possible and improves on an earlier f(t)k bound proved by Fiorini, Joret, and Wood (2013) with some very fast growing function f(t). Our proof is moreover very short and simple.

Joint work with Vida Dujmović, Gwenaël Joret, and Pat Morin

08.11.2023 16:15
Torsten Ueckerdt
Karlsruhe Institute of Technology
When Surrounding is not Catching in Cops and Robber

After a short introduction of the classical game of Cops and Robber on graphs, we shall discuss two recently introduced variants in which the robber only loses when he is completely surrounded by the cops. In the first variant the robber is surrounded when he sits at a vertex v and there is at least one cop on each neighbor of v. In the second variant cops occupy edges of the graph and the robber (still moving on vertices) is surrounded if he sits at a vertex v and there is at least one cop on each incident edge at v. We shall compare these games with each other and also with the classical game in which the robber is already caught when one cop sits on the same vertex as the robber.

25.10.2023 16:15
Torsten Mütze
University of Warwick
A book proof of the middle levels theorem

In this lecture I present an elementary and fully self-contained proof of the middle levels conjecture (now theorem), which asserts that the subgraph of the (2n+1)-dimensional hypercube induced by all bitstrings with Hamming weight n or n+1 admits a Hamilton cycle for every n1.

18.10.2023 16:15
Marcelo Campos
University of Oxford
An exponential improvement for diagonal Ramsey

The Ramsey number R(k) is the minimum n such that every red-blue colouring of the edges of the complete graph Kn on n vertices contains a monochromatic copy of Kk. We prove that R(k)≤3.99k. This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in 1935.


This is joint work with Simon Griffiths, Robert Morris, Julian Sahasrabudhe.

11.10.2023 16:15
Krzysztof Potępa
Jagiellonian University
Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs

We develop a framework for algorithms finding diameter in graphs of bounded distance Vapnik-Chervonenkis dimension, in (parameterized) sub-quadratic time complexity. The class of bounded distance VC-dimension graphs is wide, including, e.g. all minor-free graphs.

We build on the work of Ducoffe et al., improving their technique. With our approach the algorithms become simpler and faster, working in Õ(k·V1-1/d·E) time complexity, where k is the diameter, d is the VC-dimension. Furthermore, it allows us to use the technique in more general setting. In particular, we use this framework for geometric intersection graphs, i.e. graphs where vertices are identical geometric objects on a plane and the adjacency is defined by intersection. Applying our approach for these graphs, we answer a question posed by Bringmann et al., finding a Õ(n7/4) parameterized diameter algorithm for unit square intersection graph of size n, as well as a more general algorithm for convex polygon intersection graphs.

This is joint work with Lech Duraj and Filip Konieczny.

04.10.2023 16:15
Avi Wigderson
Institute for Advanced Study, Princeton
The Value of Errors in Proofs

Recently, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title "MIP* = RE", surprising and impacting not only complexity theory but also some areas of math and physics. Specifically,  it resolved, in the negative, the "Connes' embedding conjecture" in the area of von-Neumann algebras, and the "Tsirelson problem" in quantum information theory. It further connects Turing's seminal 1936 paper which defined algorithms to Einstein's 1935 paper with Podolsky and Rosen which challenged quantum mechanics. You can find the paper here https://arxiv.org/abs/2001.04383

As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we'll take a meandering jurney through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (of both problems and proofs) by algorithmic efficiency, naturally leads to the genaration of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties.

The talk does not require special mathematical background.

14.06.2023 16:15
Fabrizio Frati
Università Roma Tre
Currents Trends and Hot Problems in Graph Drawing

In this expository talk, I will discuss the topics that have attracted the most attention in the graph drawing community in recent years. The talk will try to convey the direction where the research in graph drawing is going, with a focus on the most intriguing open problems in the field.

07.06.2023 16:15
Michał Seweryn
Université Libre de Bruxelles
Recent results in graph product structure theory

Graph product structure theory describes complicated graphs as subgraphs of strong products of simpler building blocks. Usually, the strong product involves three graphs: a graph of bounded treewidth, a small complete graph, and a path. For example, Dujmović et al. showed that every planar graph is a subgraph of the strong product of a treewidth-3 graph, a complete graph on three vertices, and a path. This theorem has been the key to solving many long-standing problems about planar graphs, and is arguably the most important result of the graph product structure theory.

In my talk I will discuss some of the recent results in this field. First I will discuss two generalizations of the product structure theorem for planar graphs to k-planar graphs and k-powers of planar graphs with bounded degree. The distinguishing property of these theorems is that the bound on the treewidth in the product is an absolute constant independent of k and the maximum degree. Then, I will discuss some product structure theorems, where an n-vertex graph is a subgraph of the strong product of two graphs: a graph of constant treewidth, and a complete graph on O(n) vertices. These theorems are qualitative strengthenings of √n-separator theorems by Lipton-Tarjan and Alon-Seymour-Thomas.  

Joint works with Marc Distel, Vida Dujmović, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, and David Wood

31.05.2023 16:15
Ola Svensson
École Polytechnique Fédérale de Lausanne
The Price of Explainability for Clustering
Given a set of points in d-dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worst-case ratio between the cost of the best explainable clusterings to that of the best clusterings.
 
We show that the price of explainability for k-medians is at most 1+Hk−1; in fact, we show that the popular Random Thresholds algorithm has exactly this price of explainability, matching the known lower bound constructions. We complement our tight analysis of this particular algorithm by constructing instances where the price of explainability (using any algorithm) is at least (1−o(1))·ln k, showing that our result is best possible, up to lower-order terms. We also improve the price of explainability for the k-means problem to O(k·lnln k) from the previous O(k·ln k), considerably closing the gap to the lower bounds of Ω(k).
 
Finally, we study the algorithmic question of finding the best explainable clustering: We show that explainable k-medians and k-means cannot be approximated better than O(ln k), under standard complexity-theoretic conjectures. This essentially settles the approximability of explainable k-medians and leaves open the intriguing possibility to get significantly better approximation algorithms for k-means than its price of explainability.
 
This is joint work with Anupam Gupta, Madhusudhan Reddy Pittu, and Rachel Yuan
24.05.2023 16:15
Csaba Tóth
California State University, Northridge
Optimal spanners in Euclidean spaces

For a set S of n points in a metric space (X,d) and a parameter t>1, a t-spanner is a weighted graph G=(S,E) such that the shortest path distance in G approximates the pairwise distances in the metric space up to a factor of at most t (stretch factor). This talk focuses on the d-dimensional Euclidean space in the regime where t is close to 1. Recent research uncovered tight trade-offs for two important quality measures for t-spanners: the sparsity |E(G)|/n and the lightness w(G)/w(MST(S)). We present an algorithm that constructs a t-spanner for a given set of n points in Euclidean d-space, by sparsifying classical Yao-graphs, that attains a worst-case optimal bound on the weight of the spanner.

In the online model, a sequence of points arrive one-by-one, and we need to maintain a t-spanner for the first n points for all n. By combining sparse Yao-graphs and hierarchical clustering, we obtain an online algorithm that maintains a light spanner and achieves logarithmic competitive ratio compared to the offline optimum.

17.05.2023 16:15
John Iacono
Université Libre de Bruxelles
The pursuit of the dynamic optimality conjecture via the geometry of binary search trees

In 1983, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based search tree algorithm on every sufficiently long sequence — any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. In doing so we will present the geometric view of binary search trees, introduced in 2009, where we (with Erik D. Demaine, Dion Harmon, Daniel M. Kane and Mihai Pătraşcu) showed an equivalence between binary search tree algorithms and a simple combinatorial property of points in the plane. Almost all recent progress, which we will survey, towards the forty-year-old dynamic optimality conjecture since then has used this view, as it greatly simplifies reasoning about binary search trees.

10.05.2023 16:15
Clément Rambaud
École Normale Supérieure, PSL Paris
Neighborhood complexity of planar graphs

In a class of graphs of bounded expansion, for every graph in the class, for every non-empty set A of vertices, for every radius r, the number of distinct intersections between A and a ball of radius r is at most f(r)·|A| for some function f depending only on the considered class [Reidl, Sánchez Villaamil and Stravopoulos, 2019]. The function f coming from existing proofs is typically exponential. We prove that in the special case of planar graphs, f can be taken to be a polynomial, and more precisely in O(r4). We also show that a polynomial bound holds more generally for every proper minor-closed class of graphs.

This is joint work with Gwenaël Joret.

26.04.2023 16:15
David Eppstein
University of California, Irvine
The Complexity of Iterated Reversible Computation

Reversible computation has been studied for over 60 years as a way to evade fundamental physical limits on the power needed for irreversible computational steps, and because quantum computing circuits are necessarily reversible. We study a class of problems based on computing the iterated values of a reversible function. The story leads through Thomason's lollipop algorithm in graph theory, circuit complexity, and reversible cellular automata, to card shuffling, the reflections of light in jewels, and curves on topological surfaces, and involves both PSPACE-hard problems and problems with unexpected polynomial-time algorithms.

19.04.2023 16:15
Pat Morin
Carleton University
Proof of the Clustered Hadwiger Conjecture

Hadwiger's Conjecture asserts that every Kh-minor-free graph is properly (h-1)-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every Kh-minor-free graph is (h-1)-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. It solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed ts, we show that every Ks,t-minor-free graph is (s+1)-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van de Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries.

This joint work with Vida Dujmović, Louis Esperet, and David R. Wood.

12.04.2023 16:15
Ruta Mehta
University of Illinois at Urbana-Champaign
Competitive division of goods, bads, and mixed: existence, computation, and complexity

Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This age-old problem, mentioned even in the Bible, arises naturally in a wide range of real-life settings, for example, school seat assignments, partnership dissolution, sharing of satellites, and dividing costs for climate resilience. Division based on competitive equilibrium (CE) has emerged as one of the best mechanisms for this problem. The existence and computability of CE have been extensively studied when all items are disposable goods, while the problem is less explored when some of them are non-disposable chores (bads). In this talk, I will discuss recent algorithmic advances on the computation of CE when each item may be a good, a chore, or both (mixed).

I will first consider the case of additive valuations, where when all items are goods, the CE set is well-known to be captured by convex programming formulations and thereby forms a convex set. In sharp contrast, with chores, the CE set may be nonconvex and disconnected. I will discuss how to handle this non-convexity through a new exterior-point method to find an approximate CE in polynomial time (FPTAS). This method seems general enough to work with any mathematical formulation that optimizes a coordinate-wise monotone function over linear constraints. Finally, I will discuss recent developments on the exchange setting (barter system) on existence and computational complexity.

Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Jugal Garg, and Peter McGlaughlin.

05.04.2023 16:15
Ralph Keusch
Siemens Mobility CH
A Solution to the 1-2-3 Conjecture

In 2004, Karoński, Łuczak and Thomason conjectured that for each connected graph on at least 3 vertices, it is possible to assign weights from {1,2,3} to the edges such that neighboring vertices always obtain different weighted degrees. Recently, Przybyło verified the conjecture for all graphs G where the minimum degree is sufficiently large, compared to the maximum degree and to an absolute constant. In general, the best-known bound was by Kalkowski, Karoński, and Pfender from 2011. They proved that such an assignment is always possible with the weight set {1,2,3,4,5}.

We present a flow-based strategy to construct vertex-coloring edge-weightings and show how it was first used to shrink the general bound to the set {1,2,3,4} and now led to the confirmation of the conjecture.

29.03.2023 16:15
Alex Scott
University of Oxford
On a problem of El-Zahar and Erdős

Two subgraphs A,B of a graph G are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erdős in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results.

We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number. Second, we look at what happens if we replace the hypothesis that G has large chromatic number with the hypothesis that G has sufficiently large minimum degree. This, together with excluding Kt, is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding a complete graph we exclude a complete bipartite graph. Finally, we discuss analogous problems for tournaments.

This is joint work with Tung Nguyen and Paul Seymour.

22.03.2023 16:15
Martin Grohe
RWTH Aachen
A Deep Dive into the Weisfeiler-Leman Algorithm

The Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced.

In my talk, I will introduce the Weisfeiler-Leman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications.

15.03.2023 16:15
Sebastian Siebertz
Universität Bremen
Advances in algorithmic meta-theorems

Algorithmic meta-theorems provide general explanations when and why certain algorithmic problems can be solved efficiently. They are typically formulated in terms of logic (defining the descriptive complexity of the problems) and structural properties of their inputs. A prototypical algorithmic meta-theorem is Courcelle’s Theorem, stating that every graph property definable in monadic second-order logic (MSO) can be decided in linear time on every graph class of bounded treewidth. Similarly, every graph property definable in first-order logic (FO) can be tested efficiently on every nowhere dense graph class.

In this talk I will present recent progress on algorithmic meta-theorems for FO on dense graph classes as well as for logics whose expressive power lies between MSO and FO. The presented results reveal beautiful connections between structural graph theory, classical model theory and algorithmics.

08.03.2023 16:15
Sándor Kisfaludi-Bak
Aalto University
On geometric variants of TSP and Steiner tree

In the classic Euclidean traveling salesman problem, we are given n points in the Euclidean plane, and the goal is to find the shortest round trip that visits all the points. We will discuss some of the key techniques that allowed us to find (conditionally) optimal exact and approximation algorithms for this problem, while the closely related Steiner tree problem seems to resist many similar attempts. We will then turn to the traveling salesman or Steiner tree with "neighborhoods". Here instead of points, we are given a set of affine subspaces, and the goal is to find the shortest round trip or tree that intersects each subspace. It turns out that these problems have a different computational complexity than the classic problems with points: they require a completely novel approach for the hyperplane case, while the other cases remain largely unresolved.

01.03.2023 16:15
Mikkel Thorup
University of Copenhagen
Reconstructing the Tree of Life (Fitting Distances by Tree Metrics)

We consider the numerical taxonomy problem of fitting an SxS distance matrix D with a tree metric T. Here T is a weighted tree spanning S where the path lengths in T induce a metric on S. If there is a tree metric matching D exactly, then it is easily found. If there is no exact match, then for some k, we want to minimize the Lk norm of the errors, that is, pick T so as to minimize ||D-T||k = (Σi,jϵS |D(i,j)-T(i,j)|k) 1/k.

An evolutionary tree induces a hierarchical classification of species and this is not just tied to biology. Medicine, ecology and linguistics are just some of the fields where this concept appears, and it is even an integral part of machine learning and data science. Fundamentally, if we can approximate distances with a tree, then they are much easier to reason about: many questions that are NP-hard for general metrics can be answered in linear time on tree metrics. In fact, humans have appreciated hierarchical classifications at least since Plato and Aristotle (350 BC).

The numerical taxonomy problem is important in practice and many heuristics have been proposed. In this talk we will review the basic algorithmic theory, results and techniques, for the problem, including the most recent result from FOCS'21 [Vincent Cohen-Addad et al., 2021]. They paint a varied landscape with big differences between different moments, and with some very nice open problems remaining.

- At STOC'93, Farach, Kannan, and Warnow [Martin Farach et al., 1995] proved that under L, we can find the optimal ultrametric. Almost all other variants of the problem are APX-hard

- At SODA'96, Agarwala, Bafna, Farach, Paterson, and Thorup [Richa Agarwala et al., 1999] showed that for any norm Lk, k1, if the best ultrametric can be α-approximated, then the best tree metric can be 3α-approximated. In particular, this implied a 3-approximation for tree metrics under L∞.

- At FOCS'05, Ailon and Charikar [Nir Ailon and Moses Charikar, 2011] showed that for any Lk, k1, we can get an approximation factor of O(((log n)(log log n))1/k) for both tree and ultrametrics. Their paper was focused on the L1 norm, and they wrote "Determining whether an O(1) approximation can be obtained is a fascinating question".

- At FOCS'21, Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup [Vincent Cohen-Addad et al., 2021] showed that indeed a constant factor is possible for L1 for both tree and ultrametrics. This uses the special structure of L1 in relation to hierarchies.

- The status of Lk is wide open for 1<k<∞. All we know is that the approximation factor is between Ω(1) and O((log n)(log log n)).

25.01.2023 16:15
Andrzej Grzesik
Jagiellonian
Turán-type problems for directed cycles

A standard Turán problem for a graph F is to determine the maximal number of edges in a graph not containing F as a subgraph. This problem for directed cycles in oriented graphs is trivial, but its various generalizations, when one asks for minimum outdegree or number of other subgraphs, occurred to be hard problems. In particular, finding minimum outdegree (or semidegree) forcing an oriented graph to contain a directed triangle is a Caccetta-Häggkvist conjecture, which is open for 45 years despite numerous partial results. During the talk we will present a solution (obtained with Jan Volec) to a conjecture of Kelly, Kühn and Osthus on the minimum semidegree forcing an oriented graph to contain a directed cycle of any given length at least four. We will also discuss results (obtained jointly with Justyna Jaworska, Bartłomiej Kielak and Tomasz Ślusarczyk) for the generalized Turán problem for directed cycles when one maximizes the number of directed cycles of some other length.

18.01.2023 16:15
Tuukka Korhonen
University of Bergen
An improved parameterized algorithm for treewidth

Treewidth is a fundamental graph parameter that, informally, characterizes how tree-like a graph is. We give a 2O(k^2)·nO(1) time algorithm for determining if the treewidth of a given n-vertex graph is at most k and outputting the corresponding tree decomposition. This resolves the long-standing open problem of whether there is a 2o(k^3)·nO(1) time algorithm for treewidth. In particular, this is the first improvement on the dependency on k in fixed-parameter algorithms for treewidth since the 2O(k^3)·nO(1) time algorithm given in 1991 by Bodlaender and Kloks, and independently, by Lagergren and Arnborg. We also give a kO(k/ε)·nO(1) time (1+ε)-approximation algorithm for treewidth.

Joint work with Daniel Lokshtanov.

11.01.2023 16:15
Jonathan Narboni
Jagiellonian
Vizing's Conjecture Holds

In 1964 Vizing proved that to properly color the edges of a graph G, one need at most ∆+1 colors, where ∆ is the maximum degree of G. In his paper, Vizing actually proves that one can transform any proper edge coloring into a (∆+1)-edge-coloring using only Kempe changes. Soon after his paper, he asked the following question: is an optimal edge-coloring always reachable from any proper edge-coloring using only Kempe changes? Bonamy & al. proved that the conjecture holds for triangle free graphs, following their work, we prove that it holds for all graphs.

04.01.2023 16:15
Michał Pilipczuk
University of Warsaw
Flipper games for monadically stable classes of graphs

We will provide a gentle introduction to the on-going work on constructing a structural theory for graph classes defined by forbidding obstructions definable in logic. The focus will be on monadically stable classes of graphs: classes where one cannot define arbitrary long total orders using a fixed first-order formula. We will review recent advances on characterizing these classes in a purely combinatorial manner, in particular through a game model: the Flipper game.

21.12.2022 16:15
Ross Kang
University of Amsterdam
Colouring graphs with sparse neighbourhoods

Let us say that a graph of maximum degree Δ has local density at most η if the number of edges spanning any neighbourhood is at most η·(Δ choose 2), i.e. if the edge density is no more than an η fraction of the maximum possible. What is the largest chromatic number of such graphs? When η=0, this corresponds to asking about the largest chromatic number in triangle-free graphs of maximum degree Δ. This goes back to an old question of Vizing and is the objective of a recent breakthrough of Molloy. It is natural — and also connects to various other problems in the field — to consider other choices for η. We will broadly discuss this problem, including its classic origins in Ramsey theory, and some different ideas that have recently proven fruitful.

This will touch on recent joint works with Davies, Hurley, de Joannis de Verclos, Pirot, and Sereni.

 

14.12.2022 16:15
Boris Bukh
Carnegie Mellon
Extremal graphs without exponentially-small bicliques

In 1954 Kővári, Sós, and Turán showed that every n-vertex graph not containing Ks,t has at most O(n2−1/s) edges. We construct graphs matching this bound with t≈9s, improving on factorial-type bounds. In this talk, I will explain probabilistic and geometric ideas behind the construction.

07.12.2022 16:15
László Végh
London School of Economics
Interior point methods are not (much) worse than Simplex

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2n n1.5 log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.

The number of iterations of our algorithm is at most O(n1.5 log n) times the number of segments of any piecewise linear curve in the wide neighbourhood of the central path. In particular, it matches the number of iterations of any path-following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths.

This is joint work with Xavier Allamigeon (INRIA/Ecole Polytechnique), Daniel Dadush (CWI Amsterdam), Georg Loho (U Twente), and Bento Natura (LSE/Georgia Tech).

30.11.2022 16:15
Małgorzata Sulkowska
Wrocław University of Technology
Modularity of minor-free graphs
Modularity is a well-established parameter measuring the presence of community structure in the graph. It was introduced by Newman and Girvan in 2004. Nowadays it is widely used as a quality function for community detection algorithms. The popular heuristic clustering algorithms (e.g., Louvain algorithm or Leiden algorithm) find a partition using modularity-based approach. We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, for every ε>0, the modularity of any graph in the class with sufficiently many edges is at least 1−ε. This completes the classification of maximally modular classes among all commonly considered subclasses of nowhere dense graphs with maximum degree sublinear in the number of edges.
 
Joint work with Michał Lasoń
23.11.2022 16:15
Sophie Spirkl
University of Waterloo
Induced subgraphs and treewidth: H-free graphs

Treewidth is an important measure of the “complexity” of a graph, and as part of the Graph Minors project, Robertson and Seymour characterized unavoidable subgraphs of graphs with large treewidth. Here we are interested in unavoidable induced subgraphs instead. In this context, Lozin and Razgon characterized all finite families F of graphs such that F-free graphs have bounded treewidth. I will talk about related result, characterizing which graphs H have the property that excluding H as well as four families of large treewidth (a complete graph, a complete bipartite graph, all subdivisions of a wall, and their line graphs) as induced subgraphs leads to a class of bounded treewidth.

Joint work with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, and Sepehr Hajebi

16.11.2022 16:15
Hoang La
Jagiellonian
On Barnette's Conjecture for directed graphs

Knauer and Valicov showed that multiples conjectures from seemingly different problems all fit into the same framework of cuts in matchings of 3-connected cubic graphs. They unite Tait's, Barnette's, and Tutte's conjectures on Hamiltonicity in cubic graphs, Neumann-Lara's on the dichromatic number of planar graphs, and Hochstättler's on contraction of even digraphs. More precisely, these are all equivalent to conjectures of the form ''Every 3-connected, cubic, bipartite/planar/directed graph contains a perfect matching without (directed) cut''. If you drop two of these restrictions (bipartite, planar, directed), then the conjecture is false. If you drop one or none, then the conjecture remains open. We are investigating the dual version of the conjecture with all three restrictions, namely ''Every directed planar Eulerian triangulation can be vertex-partitioned into two acyclic sets''. This new framework can be useful as a planar Eulerian triangulation has an unique partition into three independent sets.

09.11.2022 16:15
Wojciech Czerwiński
University of Warsaw
Reachability problem in Vector Addition Systems

Recently we managed with co-authors to settle the complexity of the reachability problem for Vector Addition Systems (VASes) to be Ackermann-complete. Despite of that the combinatorics of VASes still remains mysterious and there is a bunch of very natural problems about which we know shockingly little. The focus of my talk will be on tools. I will present techniques, which led to the proof of Ackermann-hardness for the reachability problem and which hopefully may help in solving the remaining challenges.

02.11.2022 16:15
Jędrzej Hodor
Jagiellonian
Dimension of planar posets

It is a longstanding open problem if posets with a planar cover graph are dim-bounded (meaning that large dimension yields a large standard example as a subposet). This notion is the posets' counterpart of the well-studied χ-boundedness in the graph theory. In my talk, I will focus on summarizing the new progress in this area. The dim-boundedness was recently proved for posests with planar diagram and for posets with planar cover graph and a zero. I will try to sketch some ideas standing behind these results. The other interesting related question in the area is the following. Suppose that a planar poset has a large standard example as a subposet, then, how does this standard example look like? There are two canonical constructions of planar posets with large standard example contained, namely, Kelly's example and Trotter's wheel. We believe that these are (in a structural sense) the only ways to draw a standard example on the plane. For example, we proved that a poset with a planar cover graph, a zero, and large dimension contains a large Trotter's wheel.

The list of coauthors of substantial results that are going to be discussed in my talk: P.Micek, M.Seweryn, H.S.Blake, W.T.Trotter

26.10.2022 16:15
Dömötör Pálvölgyi
Eötvös Loránd University
At most 3.55^n stable matchings

We improve the upper bound for the maximum possible number of stable matchings among n jobs and n applicants (formerly known as n men and n women) from 131072n to 3.55n. To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects.

Joint work with Cory Palmer

19.10.2022 16:15
Vida Dujmović
University of Ottawa
Stack and Queue layouts

This talk will focus on two graph parameters: stack layouts (aka. book embeddings) and queue layouts of graphs. I will talk about the history of these two graph parameters, their  still not fully understood relationship and some recent breakthroughs.

12.10.2022 16:15
Friedrich Eisenbrand
École Polytechnique Fédérale de Lausanne
Integer programming with few constraints

The talk features a survey as well as recent new results on two independent approaches to derive efficient algorithms for integer programming, namely algorithms based on the geometry of numbers and dynamic programming techniques, with an extra spotlight on the case in which the number of constraints (apart from bounds on the variables) is small. We will highlight open problems and possible future directions.

The presented  results of the speaker have been jointly achieved with Daniel Dadush, Thomas Rithvoss and Robert Weismantel.

05.10.2022 16:15
Paul Seymour
Princeton University
Getting closer to the Erdős-Hajnal conjecture
A general n-vertex graph may not have a clique or stable set larger than O(log n), but excluding an induced subgraph makes a significant difference. The Erdős-Hajnal conjecture (from 1977) says that for every graph H, there exists c such that every H-free graph G (that is, not containing H as an induced subgraph) has a clique or stable set of size at least |G|c. This is still open, and is notoriously intractable.


Erdős and Hajnal proved a general bound: for every H there exists c>0 such that every H-free graph has a clique or stable set of size at least exp(c (log|G|)1/2). This is still the record for most graphs H, but in some instances one can do better. Let us say H is "friendly" if there exists c>0 such that every H-free graph G has a clique or stable set of size at least exp(c (log|G| loglog|G|)1/2). We prove that many graphs are friendly – for instance, all split graphs are friendly, and so is the eight-vertex path, and all graphs obtained from a cograph by adding a new vertex joined arbitrarily.

Joint work with Matija Bucić, Tung Nguyen and Alex Scott

15.06.2022 16:15
Piotr Micek
Jagiellonian
Boolean dimension and dim-boundedness of posets with a unique minimal element whose cover graphs are planar

In 1989, Nešetřil and Pudlák posed the following challenging question: Do planar posets have bounded Boolean dimension?  We show that every poset with a planar cover graph and a unique minimal element has Boolean dimension at most 13. As a consequence, we are able to show that there is a reachability labeling scheme with labels consisting of O(log n) bits for planar digraphs with a single source. The best known scheme for general planar digraphs uses labels with O(log2n) bits [Thorup, JACM 2004], and it remains open to determine whether a scheme using labels with O(log n) bits exists. The Boolean dimension result is proved in tandem with a second result showing that the dimension of a poset with a planar cover graph and a unique minimal element is bounded by a linear function of its standard example number. However, one of the major challenges in dimension theory is to determine whether dimension is bounded in terms of standard example number for all posets with planar cover graphs.

Within this talk after a quick introduction, I aim to lay out all the ideas behind the proof bounding Boolean dimension.

This is a joint work with Heather Smith Blake and Tom Trotter.

08.06.2022 16:15
Michał Wrona
Jagiellonian
Local consistency methods in Solving CSPs and CSP-like problems over omega-categorical structures

Feder-Vardi conjecture has been settled independently by Dmitriy Zhuk and Andrei Bulatov. What is perhaps even more interesting, though, is that they not only confirmed the complexity (Feder-Vardi) conjecture, i.e., CSP(B) for a finite structure B is either in P or it is NP-complete, but they also confirmed the algebraic dichotomy conjecture describing  tractable B in terms of operations preserving B.

A similar algebraic dichotomy conjecture called an infinite algebraic dichotomy conjecture has been established for CSP(B) over first-order reducts B of finitely bounded homogeneous structures, all of which are in particular omega-categorical. Despite recent advances towards solving this dichotomy, it still seems to be wide open. One of the reasons is probably that local consistency  and similar algorithmic techniques are in this context not yet fully understood. This step seems to be crucial since the characterization of finite-domain CSP solvable by local consistency  is considered as a major step towards the resolution of the dichotomy.

In this talk, I will survey the results on the local consistency methods in solving CSP and CSP-like problems over omega-categorical structures.

25.05.2022 16:15
Szymon Toruńczyk
University of Warsaw
Ordered graphs of bounded twin-width and monadically NIP graph classes

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.

This has several consequences.First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh, Bollobás, and Morris [Eur. J. Comb. '06] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width.

Those results are joint work with Bonnet, Giocanti, Ossona de Mendez, Simon, Thomasse, accepted to STOC'22.

Time permitting, I will also discuss the more general landscape of monadically NIP graph classes, generalizing both nowhere dense classes and classes of bounded twin-width.

18.05.2022 16:15
Rose McCarty
University of Warsaw
Circuit decompositions of group-labelled graphs

This talk focuses on Eulerian graphs whose arcs are directed and labelled in a group. Each circuit yields a word over the group, and a circuit is non-zero if this word does not evaluate to 0. We give a precise min-max theorem for the following problem. Given a vertex v, what is the maximum number of non-zero circuits in a circuit-decomposition where each circuit begins and ends at v?

This is joint work with Jim Geelen and Paul Wollan. Our main motivation is a surprising connection with vertex-minors which is due to Bouchet and Kotzig.

11.05.2022 16:15
Michał Seweryn
Jagiellonian
Forcing walls with divisibility constraints

An n-wall is a graph obtained from the square grid with n rows and 2n columns by deleting every odd vertical edge in every odd row and even vertical edge in every even row, then deleting the two resulting vertices of degree 1, and finally subdividing each edge any number of times. Thomassen showed that there exists a function f(n,m) such that every f(n,m)-wall contains an n-wall such that every path between two branch vertices has length divisible by m. We study the asymptotics of the optimal such function f(n,m). For odd m we show that f(n,m) = O(n·poly(m)). In the case m=2, we obtain a bound f(n, 2) = O(n·log n).

This is joint work with Piotr Micek, Raphael Steiner and Sebastian Wiederrecht.

04.05.2022 16:15
Jakub Kozik
Jagiellonian
Deterministic Constructions of 3-Chromatic Hypergraphs with Few Edges

How many edges do we need to build a k-uniform hypergraph that cannot be properly two colored? Using the probabilistic argument Erdös proved in 1964, that there exist such hypergraphs with roughly k2·2k edges. However, without a random source at hand, the sizes that we can achieve by efficient procedures are much larger. The first and only known explicit construction with 2k+o(k) edges was proposed by Gebauer in 2013. We will discuss how it can be improved first by randomizing and then derandomizing it once more.

27.04.2022 16:15
Andrew Suk
University of California at San Diego
Unavoidable patterns in simple topological graphs

A simple topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by non-self-intersecting arcs connecting the corresponding points, with the property that any two edges have at most one point in common. In 2003, Pach-Solymosi-Tóth showed that every n-vertex complete simple topological graph contains a topological subgraph on m = Ω(log n) vertices that is weakly isomorphic to the complete convex geometric graph or to the complete twisted graph on m vertices. Here,  we improve this bound to  (log n)1/4−o(1). I will also discuss other related problems as well.

This is joint work with Ji Zeng.

20.04.2022 16:15
Sergey Norin
McGill University
Brambles, stack number and topological overlap

A (strict) bramble in a graph G is a collection of subgraphs of G such that the union of any number of them is connected. The order of a bramble is the smallest size of a set of vertices that intersects each of the subgraphs in it. Brambles have long been part of the graph minor theory toolkit, in particular, because a bramble of high order is an obstruction to existence of  a low width tree decomposition.

We will discuss two dimensional analogues of brambles. In particular, we show that a bramble of high order in a two-dimensional simplicial complex X is an obstruction to existence of a low multiplicity continuous map from X  to the plane (and more generally to any two-dimensional collapsible complex). As an application, we show that strong products of three paths have unbounded stack number.

Based primarily on joint work with David Eppstein,  Robert Hickingbotham, Laura Merker, Michał T. Seweryn and David R. Wood. (https://arxiv.org/abs/2202.05327)

13.04.2022 16:15
Alex Scott
University of Oxford
Induced subgraphs of induced subgraphs of large chromatic number

We prove that for every graph F with at least one edge there is a constant cF and there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most cF. (Here a graph is F-free if it does not contain an induced copy of F.) This generalizes theorems of Briański, Davies and Walczak, and of Carbonero, Hompe, Moore and Spirkl.  We further show an analogous statement where clique number is replaced by odd girth.

Joint work with Antonio Girao, Freddie Illingworth, Emil Powierski, Michael Savery, Youri Tamitegama and Jane Tan.

06.04.2022 16:15
Marcin Briański
Jagiellonian
Separating polynomial χ-boundedness from χ-boundedness and thereabouts

If a graph contains no large complete subgraph but nonetheless has high chromatic number what can we say about the structure of such a graph? This question naturally leads to investigation of χ-bounded classes of graphs — graph classes where a graph needs to contain a large complete subgraph in order to have high chromatic number. This an active subfield of graph theory with many long standing open problems as well as interesting recent developments.

In this talk I will present a construction of a hereditary class of graphs which is χ-bounded but not polynomially χ-bounded. This construction provides a negative answer to a conjecture of Esperet that every χ-bounded hereditary class of graphs is polynomially χ-bounded. The construction is inspired by a recent paper of Carbonero, Hompe, Moore, and Spirkl which provided a counterexample to another conjecture of Esperet.

This is joint work with James Davies and Bartosz Walczak (available at arXiv:2201.08814)

30.03.2022 16:15
Raphael Steiner
ETH Zürich
New bounds for relatives of Hadwiger's conjecture

In this talk, I will present some recent results on two variants of Hadwiger's conjecture.

             First, I will discuss the so-called Odd Hadwiger's conjecture, a strengthening of Hadwiger's conjecture proposed by Gerards and Seymour in 1995. First I will show how, using a simple new trick, one can reduce the problem of coloring graphs with no odd Kt-minor to coloring graphs with no Kt-minor up to a constant factor of 2, thereby improving previous upper bounds for this problem. Then, I will outline how a similar idea can be used to significantly improve the known bounds for clustered colorings of odd Kt-minor free graphs, in which we look for (possibly improper) colorings with monochromatic components of small size.

            Second,  I will discuss the so-called List Hadwiger's conjecture,  which states that there exists a constant c such that every graph with no Kt-minor is ct-choosable (i.e.,  list colorable).   I will show a probabilistic construction of a new lower bound  2t-o(t)  for list coloring  Kt-minor free graphs,  this refutes a conjecture by Kawarabayashi and Mohar which stated that one can take c=3/2.  I will then show how some well-chosen modifications to our construction can be used to prove lower bounds also for list coloring  H-minor free graphs where  H  is non-complete. In particular, I will show that   Ks,t-minor free graphs  for large comparable  s  and  t  can have list chromatic number  at least  (1-o(1))(s+t+min(s,t)),  this refutes a 2001 conjecture by Woodall.

23.03.2022 16:15
Mathieu Mari
University of Warsaw and IDEAS-NCBR
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles

We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [2021] obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs), without intersecting certain special horizontal line segments called fences.

In this talk, I will present a (2+ϵ)-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 4. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to 2+ϵ. In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to O(1/ϵ) line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR.

At the end of the talk, I will present a bunch of open questions related to the problem.

This is a joint work with Waldo Gálvez, Arindam Khan, Tobias Mömke, Madhusudhan Reddy and Andreas Wiese
16.03.2022 16:15
Marek Sokołowski
University of Warsaw
Graphs of bounded twin-width are quasi-polynomially χ-bounded

We prove that for every t∈ℕ there is a constant γ(t) such that every graph with twin-width at most t and clique number ω has chromatic number bounded by 2γ(t) log^{4t+3} ω. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially χ-bounded. This provides a significant step towards resolving the question of Bonnet et al. [ICALP 2021] about whether they are polynomially χ-bounded.

This is a joint work with Michał Pilipczuk

09.03.2022 16:15
Pat Morin
Carleton University
Free Sets in Planar Graphs

A k-vertex set S of vertices in a planar graph G is free if, for any k-point set X, there exists a non-crossing straight-line drawing of G with the vertices of S mapped to the points in X.  In this talk we survey the history and applications of free sets and present two recent results [1,2]:

1. Free sets and collinear sets: If G has any drawing in which all vertices of S appear on a line, then S is a free set.

2. Free sets and dual circumference:  If G has bounded degree, then the size of the largest collinear set in G is proportional to the length of the longest cycle in the dual of G.

[1] Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, and Günter Rote: Every collinear set in a planar graph is free. Discrete & Computational Geometry, 65:999–1027, 2021.

[2] Vida Dujmovic, Pat Morin: Dual Circumference and Collinear Sets. SoCG 2019: 29:1-29:17.

02.03.2022 16:15
Jarosław Byrka
University of Wrocław
Online Facility Location with Linear Delay

We study the problem of online facility location with delay. In this problem, a sequence of n clients appear in the metric space, and they need to be eventually connected to some open facility. The clients do not have to be connected immediately, but such a choice comes with a penalty: each client incurs a waiting cost (the difference between its arrival and connection time). At any point in time, an algorithm may decide to open a facility and connect any subset of clients to it. This is a well-studied problem both of its own, and within the general class of network design problems with delays.
Our main focus is on a new variant of this problem, where clients may be connected also to an already open facility, but such action incurs an extra cost: an algorithm pays for waiting of the facility (a cost incurred separately for each such "late" connection). This is reminiscent of online matching with delays, where both sides of the connection incur a waiting cost. We call this variant two-sided delay to differentiate it from the previously studied one-sided delay.
We present an O(1)-competitive deterministic algorithm for the two-sided delay variant. On the technical side, we study a greedy strategy, which grows budgets with increasing waiting delays and opens facilities for subsets of clients once sums of these budgets reach certain thresholds. Our technique is a substantial extension of the approach used by Jain, Mahdian and Saberi [STOC 2002] for analyzing the performance of offline algorithms for facility location.
We then show how to transform our O(1)-competitive algorithm for the two-sided delay variant to O(logn/loglogn)-competitive deterministic algorithm for one-sided delays. We note that all previous online algorithms for problems with delays in general metrics have at least logarithmic ratios.

Joint work with Marcin Bienkowski, Martin Böhm and Jan Marcinkowski

26.01.2022 16:15
Sławomir Lasota
University of Warsaw
Improved Ackermannian lower bound for the reachability problem of vector addition systems
Vector addition systems, equivalent to Petri nets, are an established model of concurrency with widespread applications. The reachability problem, where we ask whether from a given initial configuration there exists a sequence of valid execution steps reaching a given final configuration, is the central algorithmic problem for this model. The complexity of the problem has remained, until recently, one of the hardest open questions in verification of concurrent systems. A first upper bound has been provided only in 2015 by Leroux and Schmitz, then refined by the same authors to Ackermannian upper bound in 2019. The exponential space lower bound, shown by Lipton already in 1976, remained the only known for over 40 years until a breakthrough non-elementary lower bound by Czerwiński et al in 2019. Finally, a matching Ackermannian lower bound announced in 2021 by Czerwiński and Orlikowski, and independently by Leroux, established the complexity of the problem.
 
I will present an improvement of the former construction, making it conceptually simpler and more direct and, on the way, improving the lower bound for vector addition systems  in fixed dimension (or, equivalently, Petri nets with fixed number of places).
19.01.2022 16:15
James Davies
University of Waterloo
Ringel's circle problem

A constellation is a finite collection of circles in the plane in which no three circles are tangent at the same point. In 1959, Ringel asked how many colours are required to colour the circles of a constellation so that tangent circles receive different colours. We present a solution to Ringel's circle problem by constructing constellations that require arbitrarily many colours.

Joint work with Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak

12.01.2022 16:15
Grzegorz Gutowski
On a problem of Steinhaus

In this talk, inspired by a "17-points" problem of Steinhaus (Problems 6 and 7 from his book "Sto zadań"), we discuss infinite sequences of real numbers in [0,1).
For a function f:N--->N, we say that a sequence X is f-piercing if for every finite m, the first f(m) elements of X contain at least one element in every interval [i/m,(i+1)/m) for i from 0 up to m-1. There is a nice construction of (m/ln2)-piercing sequence due to de Bruijn and Erdős which satisfies even stronger piercing properties. We are able to show that this is best possible, as there are no (am+o(m))-piercing sequences for a<1/ln2. Our results allow for some new tight linear bounds for similar concepts defined for finite sequences.

The talk is based on the manuscript: https://arxiv.org/abs/2111.01887

15.12.2021 16:15
Lars Rohwedder
EPFL
A (2+ϵ)-approximation algorithm for preemptive weighted flow time on a single machine

In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I [STOC'21] managed to improve this large unspecified constant to (2+ϵ). I will give a very graphic presentation of the algorithmic techniques behind this.

08.12.2021 16:15
István Tomon
ETH Zürich
Ramsey properties of semilinear graphs

A graph G is semilinear of complexity t if the vertices of G are points in some real space, and the edges of G are determined by the sign-patterns of t linear functions. Many natural geometric graph families are semilinear of bounded complexity, e.g. intersection graphs of boxes, shift graphs, interval overlap graphs. There is a long line of research studying the exceptional Ramsey and coloring properties of such geometric graphs; I will show that many of these results can be traced back to their semilinear nature.

01.12.2021 16:15
Barnaby Martin
Durham University
QCSP monsters and the future of the Chen Conjecture

We elaborate the complexity of the Quantified Constraint Satisfaction Problem, QCSP(A), where A is a finite idempotent algebra. Such a problem is either in NP or is co-NP-hard, and the borderline is given precisely according to whether A enjoys the polynomially-generated powers (PGP) property. This completes the complexity classification problem for QCSPs modulo that co-NP-hard cases might have complexity rising up to Pspace-complete. Our result requires infinite languages, but in this realm represents the proof of a slightly weaker form of a conjecture for QCSP complexity made by Hubie Chen in 2012. The result relies heavily on the algebraic dichotomy between PGP and exponentially-generated powers (EGP), proved by Dmitriy Zhuk in 2015, married carefully to previous work of Chen. Finally, we discuss some recent work with Zhuk in which the aforementioned Chen Conjecture is actually shown to be false. Indeed, the complexity landscape for QCSP(B), where B is a finite constraint language, is much richer than was previously thought.

24.11.2021 16:15
Jan Derbisz
Circular-arc graphs and the Helly property

Circular-arc graphs, defined as the intersection graphs of arcs of a fixed circle, are probably one of the simplest classes of intersection graphs, which does not satisfy the Helly property in general (i.e. there are circular-arc graphs in which some cliques can be represented by arcs whose common intersection is empty). In particular, some cliques of a circular-arc G graph may satisfy the Helly property in some but not all circular-arc representations of G.

In the Helly Clique Problem, for a given circular-arc graph G and some of its cliques C1,...,Ck (not necessarily maximal in G) one needs to decide whether there exists a circular-arc representation of G in which all the cliques C1,...,Ck satisfy the Helly property. We know that the Helly Clique Problem is NP-complete and, under the ETH, it can not be solved in time 2o(k)poly(n), where n is the number of vertices of G (Ağaoğlu et al.).

In the talk we will consider the Helly Clique Problem in the context of parameterized complexity, where the natural parameter is the number of cliques given in the input. We will show that the Helly Clique Problem:
- admits an algorithm with running time 2O(k log k)poly(n) (and hence it belongs to FPT),
- admits a polynomial kernel of size O(k6).

Moreover, we will discuss the relation of the Helly Clique Problem with the recognition problems of so-called H-graphs; in particular, in the context of those graphs H for which the recognition problem remains open.

This is joint work with T. Krawczyk. The talk also includes joint work with D. Ağaoğlu, O. Cagrici, T. Hartmann, P. Hliněný, J. Kratochvíl, T. Krawczyk, and P. Zeman.

17.11.2021 16:15
Nicolas Bousquet
CNRS, Lyon
Local certification of/on sparse graph classes

Local certification consists in assigning labels to the nodes of a graph in order to certify that some given property is satisfied, in such a way that the labels can be checked locally. In this talk, our goal is to certify that a graph G belongs to a given graph class. Such certifications exist for many sparse graph classes such as trees, planar graphs and graphs embedded on surfaces with labels of logarithmic size. It is open if such a certificate exist for any H-minor free graph class. We present some generic tools which allow us to certify the H-minor-free graphs (with logarithmic labels) for each small enough H.

More generally, we consider classes defined by any MSO formula (i.e. the MSO-model checking problem), and show a local version of the well-known Courcelle theorem: in bounded treedepth graphs, logarithmic certificates can be obtained for any MSO formula. We will also discuss many open problems related to  local certification of/on sparse graph classes.

Joint works with Laurent Feuilloley and Théo Pierron

10.11.2021 16:15
Zdeněk Dvořák
Charles University
On asymptotic dimension of planar and geometric graphs

A graph class C has asymptotic dimension at most d if for every r, the r-th distance power of any graph from C can be colored by d+1 colors so that every monchromatic connected subgraph has bounded weak diameter. In a recent breakthrough result, Bonamy, Bousquet, Esperet, Groenland, Liu, Pirot, and Scott proved that all proper minor-closed classes have asymptotic dimension at most two.  We investigate some questions motivated by this result for planar graphs and geometric intersection graphs.

Joint work with Sergey Norin

03.11.2021 16:15
Torsten Mütze
University of Warwick & Charles University
Efficient generation of elimination trees and Hamilton paths on graph associahedra
An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G−x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they are closely related to centered colorings and tree-depth. They also encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm (see www.combos.org/elim). This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time O(m+n) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time O(1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of G if and only if G is chordal.
 
This is joint work with Jean Cardinal (ULB) and Arturo Merino (TU Berlin)
26.10.2021 11:00
David Wood
Monash University
Universality in minor-closed graph classes*

Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). János Pach (1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain an infinite complete graph as a minor. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite n-vertex subgraph has O(n1/2) treewidth (which implies the Lipton-Tarjan separator theorem). More generally, for every fixed positive integer t we construct a countable graph that contains every countable Kt-minor-free graph and has the above key properties.

Joint work with Tony Huynh, Bojan Mohar, Robert Šámal and Carsten Thomassen

exceptionally: Tuesday at 11:00

20.10.2021 16:15
Bartłomiej Kielak
Inducibility of small oriented graphs

For a fixed graph H, let i(H, n) be the maximum induced density of H in any graph on n vertices. The limit i(H, n), as n goes to infinity, always exists and is called inducibility of H. Fox, Huang, and Lee proved that for almost all graphs H (think of large 'typical' graphs), inducibility of H can be obtained as the limit of induced density of H in its iterated blowups. Apart from that, inducibility is well understood only for narrow classes of graphs; in particular, it is still not determined for H being a path on 4 vertices.

Definition of inducibility can be easily adapted to different settings of combinatorial structures. In this talk, I will focus on the setting of oriented graphs and discuss the inducibility of oriented graphs on at most 4 vertices.
 
Joint work with Łukasz Bożyk and Andrzej Grzesik
13.10.2021 16:15
Daniel Kráľ
Masaryk University in Brno
Uniform Turán density of hypergraphs

In the early 1980s, Erdős and Sós, initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph H is the infimum over all d for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least d contains H. In particular, they raise the questions of determining the uniform Turán densities of K43, the complete 4-vertex 3-uniform hypergraph, and K43-, the hypergraph K43 with an edge removed. The latter question was solved only recently in [Israel J. Math. 211 (2016), 349–366] and [J. Eur. Math. Soc. 97 (2018), 77–97], while the former still remains open for almost 40 years.

Prior to our work, the hypergraph K43- was the only 3-uniform hypergraph with non-zero uniform Turán density determined exactly. During the talk, we will present the following two results:

  • We construct a family of 3-uniform hypergraphs with uniform Turán density equal to 1/27. This answers a question of Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77–97] on the existence of such hypergraphs, stemming from their result that the uniform Turán density of every 3-uniform hypergraph is either 0 or at least 1/27.
  • We show that the uniform Turán density of the tight 3-uniform cycle of length k5 is equal to 4/27 if k is not divisible by three, and equal to zero otherwise. The case k=5 resolves a problem suggested by Reiher [European J. Combin. 88 (2020), 103117].

The talk is based on results obtained jointly with (subsets of) Matija Bucić, Jacob W. Cooper, Frederik Garbe, Ander Lamaison, Samuel Mohr and David Munhá Correia.

06.10.2021 16:15
Virginia Vassilevska Williams
MIT
A refined laser method and (slightly) faster matrix multiplication

Matrix multiplication is one of the most basic linear algebraic operations outside elementary arithmetic. The study of matrix multiplication algorithms is very well motivated from practice, as the applications are plentiful. Matrix multiplication is also of great mathematical interest. Since Strassen's discovery in 1969 that n-by-n matrices can be multiplied asymptotically much faster than the brute-force O(n3) time algorithm, many fascinating techniques have been developed, incorporating ideas from computer science, combinatorics, and algebraic geometry.

The fastest algorithms over the last three decades have used Strassen's "laser method" and its optimization by Coppersmith and Winograd. The method has remained unchanged; the algorithms have differed in what the method was applied to. In recent work, joint with Josh Alman, we improve the method so that applying it to the same objects that the old method was applied to immediately yields faster algorithms. Using this new method, we obtain the theoretically fastest algorithm for matrix multiplication to date, with running time O(n2.37286).

This talk will give an overview of the main techniques and will also outline our recent improvement of the laser method.

16.06.2021 16:15
Krzysztof Turowski
Degree Distribution of Dynamic Graphs Generated by a Duplication-Divergence Models
We analyze the structure of dynamic graphs generated from duplication models in which a new vertex selects an existing vertex and copies some of its neighbors and then we add some random divergence. We analyze various graph parameters like mean degree, number of open triangles, number of triangles, number of vertices of degree k or maximum degree in a graph generated from such models. We provide asymptotic analysis of expected values and tail behavior of these parameters. We also point to further extensions of this approach towards computing symmetries in these graphs and algorithms for graph compression.
 
Joint work with Philippe Jacquet, Alan Frieze and Wojciech Szpankowski
09.06.2021 16:15
Paweł Rzążewski
Warsaw University of Technology
Treewidth of graphs with forbidden induced subgraphs

The notion of treewidth and tree decompositions plays a central role in the study of graphs with forbidden minors. Besides structural characterizations, the property of having boundedtreewidth, or a tree decomposision with certain "nice" properties, can be used algorithmically. However, until very recently, there were very few results that allowed to analyze the treewidth of graphs that exclude certain induced subgraphs. Indeed, a large clique has large treewidth, but is H-free for any graph H which is not a clique. It turns out that some intresting relations between the two worlds can be found if we additionally put some restrictions on vertex degrees - either just by bounding the maximum degree, or, in some cases, by bounding the degeneracy.

During the talk we will discuss some results of this flavor. In particular, we will show that

  • graphs of bounded degeneracy that exclude all cycles of length at least t have bounded treewidth;
  • graphs of bounded degree that exclude a fixed subdivision of the claw admit a certain type of an "*induced* grid/wall theorem": they either contain the line graph of a big subdivided wall as an *induced subgraph*, or have bounded treewidth.

 

Based on the joint work with Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and with Abrishami, Chudnovsky, and Dibek.

08.06.2021 09:00
Bartosz Walczak
Coloring polygon visibility graphs and their generalizations

The visibility graph of a polygon P is formed by the pairs of vertices u and v of P such that the segment uv is disjoint from the exterior of P. We show that the class of polygon visibility graphs is χ-bounded, thus answering a question by Kára, Pór, and Wood from 2005. Specifically, we prove the bound χ≤3⋅4ω−1. We obtain the same bound for generalizations of polygon visibility graphs in which the polygon is replaced by a curve and straight-line segments are replaced by segments in a pseudo-line arrangement. The proof is carried through in the setting of ordered graphs. In particular, we show χ-boundedness of several classes of ordered graphs with excluded ordered substructures.

Joint work with James Davies, Tomasz Krawczyk, and Rose McCarty.

This is a part of Round the World Relay in Combinatorics organized by Oxford University.

Here is the full schedule: http://people.maths.ox.ac.uk/scott/relay.htm

And the zoom link for the whole event:

https://us02web.zoom.us/j/87593953555?pwd=UWl4eTVsanpEUHJDWFo3SWpNNWtxdz09

meeting id: 875 9395 3555
password: relay

02.06.2021 16:15
Marthe Bonamy
Université de Bordeaux
Graph recolouring

Given a solution to a problem, we can try and apply a series of elementary operations to it, making sure to remain in the solution space at every step. What kind of solutions can we reach this way? How fast? This is motivated by a variety of applications, from statistical physics to real-life scenarios, including enumeration and sampling. In this talk, we will discuss various positive and negative results, in the special case of graph colouring.

26.05.2021
Piotr Kawałek
Constant depth circuits

We will overview the state-of-the-art results and techniques used in proofs of the lower bounds for constant depth circuits. We focus mostly on classes AC[0], ACC[0] and CC[0]. The most important challenges and some open problems are to be discussed.

19.05.2021 16:15
Paweł Idziak
Modular circuits satisfiability of intermediate complexity

In our paper [LICS'18] a generalization of Boolean circuits to arbitrary finite algebras was introduced and applied to sketch P versus NP-complete borderline for circuits satisfiability over algebras from congruence modular varieties. However nilpotent but not supernilpotent algebras have not been put on any side of this borderline.

This paper provides a broad class of examples, lying in this grey area, and show that, under the Exponential Time Hypothesis and Strong Exponential Size Hypothesis (saying that Boolean circuits need exponentially many modular counting gates to produce Boolean conjunctions of any arity), satisfiability over these algebras have intermediate complexity. We also sketch how these examples could be used as paradigms to fill the nilpotent versus supernilpotent gap in general.

Our examples are striking in view of the natural strong connections between circuits satisfiability and Constraint Satisfaction Problem for which the dichotomy was shown by Bulatov and Zhuk.

Joint work with Piotr Kawałek and Jacek Krzaczkowski

12.05.2021 16:15
Grzegorz Gutowski
Filling blanks in matrices to avoid singularity: progress report

Given an n-by-n generator matrix with entries being subsets of a fixed field we generate the set of all matrices with entries coming from the corresponding entries in the generator matrix. Such a set of matrices is strongly singular if each member is a singular matrix. In this talk I will survey natural generalizations and connections to other problems. In particular, I will describe algorithm by Geelen for  maximum rank matrix completion problem.

05.05.2021 16:15
Louis Esperet
Université Grenoble Alpes
Universal graphs and labelling schemes

Given a graph class C, a graph G is universal for C if it "contains" all the graphs from C. As there are several notions of containment, there are several notions of universal graphs. In this talk I'll mention two versions:

  • induced-universal graphs: here G contains all the graphs of C as induced subgraphs
  • isometric-universal graphs: here G contains isometric copies of all the graphs from C (isometric means that the distances are preserved in the embedding)

Note that an isometric copy is an induced copy, so the second notion is stronger. These notions are closely related to the notion of labelling schemes in graphs. The goal is to assign labels to the vertices of each graph G from C such that upon reading the labels of any two vertices u and v, we know some properties of u and v in G (whether they are adjacent, or their distance, or whether u is reachable from v if G is a digraph). It turns out that minimizing the size of the labels is equivalent to constructing small universal graphs, at least in the case of induced-universal graphs. For isometric-universal graphs some additional work needs to be done.

I'll survey some recent progress in this area. In particular I'll show how to construct induced-universal graphs of almost optimal size for any hereditary class, using the regularity lemma. In particular this implies almost optimal reachabilty labelling schemes in digraphs and comparability labelling schemes in posets, and the construction of an almost optimal universal poset for the class of all n-element posets (of size 2n/4+o(n)). I will also show how to construct isometric-universal graphs of size 3n+o(n) for the class of all n-vertex graphs, answering a question of Peter Winkler.

Based on joint work with Marthe Bonamy, Cyril Gavoille, Carla Groenland, and Alex Scott.

28.04.2021 16:15
Daniel Kráľ
Masaryk University in Brno
Quasirandom combinatorial structures

A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is.

We will discuss quasirandom properties of other combinatorial structures, tournaments, permutations and Latin squares in particular, and present several recent results obtained using analytic tools of the theory of combinatorial limits.

The talk is based on results obtained with different groups of collaborators, including Timothy F. N. Chan, Jacob W. Cooper, Robert Hancock, Adam Kabela, Ander Lamaison, Taísa Martins, Roberto Parente, Samuel Mohr, Jonathan A. Noel, Yanitsa Pehova, Oleg Pikhurko, Maryam Sharifzadeh, Fiona Skerman and Jan Volec.

21.04.2021 16:15
Paweł Gawrychowski
University of Wrocław
Fully Dynamic Longest Increasing Subsequence

We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under

(i) inserting an element, and

(ii) deleting an element of an array.

In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designed an algorithm that maintains an O((1/ϵ)O(1/ϵ))-approximation of LIS under both operations with worst-case update time ~O(nϵ), for any constant ϵ>0. We exponentially improve on their result by designing an algorithm that maintains a (1+ϵ)-approximation of LIS under both operations with worst-case update time ~O(ϵ−5). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification.

While this essentially settles the complexity of the approximate version of the problem, the exact version seems more elusive. The only known sublinear solution was given very recently by Kociumaka and Seddighin [STOC 2021] and takes ~O(n2/3) time per update. We show polynomial conditional lower bounds for two natural extensions of this problem: weighted LIS and LIS in any subarray.

Joint work with Wojciech Janczewski

 

14.04.2021 16:15
Michał Seweryn
Dimension of posets with k-outerplanar cover graphs

In 2015, Felsner, Trotter, and Wiechert showed that posets with outerplanar cover graphs have bounded dimension. We generalise this result to posets with k-outerplanar cover graphs. Namely, we show that posets with k-outerplanar cover graph have dimension O(k3). As a consequence, we show that every poset with a planar cover graph and height h has dimension O(h3). This improves the previously best known bound of O(h6) by Kozik, Micek and Trotter.

Joint work with Maximilian Gorsky

https://arxiv.org/abs/2103.15920

07.04.2021 16:15
Mikołaj Bojańczyk
University of Warsaw
Recognisable languages over monads
Algebraic language theory originated in the study of regular languages via semigroups, instead of automata. The advantage of the semigroup approach is a richer structural theory, e.g. Green’s theory or the Factorisation Forest Theorem. (In contrast, the structural analysis of automata seldom goes beyond such elementary notions as “cycle” or “connected component”.) In this talk, I will discuss a more abstract view on semigroups, as Eilenberg-Moore algebras over the monad of finite words (aka the list monad in programming languages). Using this abstract view, by changing the monad, one can get the appropriate notion of “semigroup” for objects beyond finite words, e.g. trees or graphs. Sometimes, even theorems can be proved using this abstract view.
 
This talk is based on the draft monograph 
31.03.2021 16:15
Andrzej Dorobisz
Local Computation Algorithms for Coloring of Uniform Hypergraphs

We present a progress on local computation algorithms for two coloring of k-uniform hypergraphs. We focus on instances that (for a parameter α) satisfy strengthened assumption of Local Lemma of the form 21-αk(Δ+1)e<1, where Δ is the bound on the maximum edge degree of the hypergraph. We discuss how previous works on the subject can be used to obtain an algorithm that works in polylogarithmic time per query for α up to about 0.139. Then, we present a procedure that, within similar bounds on running time, solves wider range of instances by allowing α to be at most about 0.227.

Joint work with Jakub Kozik

24.03.2021 16:15
Marcin Pilipczuk
University of Warsaw
Recent progress in understanding H-free graphs for H being a path or a subdivided claw

Graph classes excluding a path or a subdivided claw as an induced subgraph are so far mysterious: on one hand, beside some corner cases, they do not seem to have any good structural description, but on the other hand, a number of combinatorial problems - including Maximum Independent Set (MIS) - lack an NP-hardness proof in these graph classes, indicating a possible hidden structure that can be used algorithmically. Furthermore, graphs excluding a fixed path as an induced subgraph were one of the earliest examples of a chi-bounded graph class, with an elegant proof technique dubbed the Gyarfas' path argument. In the recent years the progress accelerated, leading to, among other results, (a) a quasi-polynomial-time algorithm for MIS in graphs excluding a fixed path as an induced subgraph, (b) a QPTAS for MIS in graphs excluding a subdivided claw as an induced subgraph, (c) the proof of the Erdos-Hajnal property in graph classes excluding a fixed forest and its complement. In the talk, I will survey these results, showing the role of the Gyarfas' path argument in most (all?) of them, and outline research directions for the future.

17.03.2021 16:15
Stefan Felsner
Technische Universität Berlin
Combinatorics of Pseudocircle Arrangements

In this talk we survey results for pseudocircle arrangements. Along the way we present several open problems. Among others we plan to touch the following topics:

 * The taxonomy of classes of pseudocircle arrangements.
 * The facial structure with emphasis on triangles and digons.
 * Circularizability.
 * Coloring problems for pseudocircle arrangements.

The talk includes work of Grünbaum, Snoeyink, Pinchasi, Scheucher, myself, and others.

10.03.2021 16:15
Bartosz Walczak
Approximating Pathwidth for Graphs of Small Treewidth

We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t log t). This is the first algorithm to achieve an f(t)-approximation for some function f.

Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th+2 has treewidth at least t or contains a subdivision of a complete binary tree of height h+1. The bound th+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c=2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Ω(kc) has treewidth at least k or contains a subdivision of a complete binary tree of height k.

Our main technical algorithm takes a graph G and some (not necessarily optimal) tree decomposition of G of width t' in the input, and it computes in polynomial time an integer h, a certificate that G has pathwidth at least h, and a path decomposition of G of width at most (t'+1)h+1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height h. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth.

 

Joint work with Carla Groenland, Gwenaël Joret, and Wojciech Nadara.

08.10.2020 12:00
Patryk Mikos
Geometric and weight constraints in Online Interval Coloring
PhD defense - room 0004
15.01.2020 16:15
Michał Seweryn
Erdös-Hajnal properties for powers of sparse graphs

The notion of nowhere dense classes of graphs attracted much attention in recent years and found many applications in structural graph theory and algorithmics. The powers of nowhere dense graphs do not need to be sparse, for instance the second power of star graphs are complete graphs. However, it is believed that powers of sparse graphs inherit somewhat simple structure. In this spirit, we show that for a fixed nowhere dense class of graphs, a positive real ε and a positive integer d, in any n-vertex graph G in the class, there are disjoint vertex subsets A and B with |A|=Ω(n) and |B|=Ω(n1-ε) such that in the d-th power of G, either there is no edge between A and B, or there are all possible edges between A and B.

 

 

Joint work with Marcin Briański, Piotr Micek and Michał Pilipczuk
11.12.2019 16:15
Adam Polak
Monochromatic triangles, intermediate matrix products, and convolutions

The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(nω) time algorithms, for ω<2.373. On the other hand, the (min,+)-product, which is at the heart of APSP, is widely conjectured to require cubic time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems, e.g. the (min,max)-product, the min-witness product, APSP in directed unweighted graphs. The best runtimes for these "intermediate" problems are all O(n(3+ω)/2). A similar phenomenon occurs for convolution problems.


Can one improve upon the running times for these intermediate problems? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way?

We make progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and min-witness product can be reduced to both the (min,max)-product and a variant of the monochromatic triangle problem. We also show that a natural convolution variant of monochromatic triangle is equivalent to the famous 3SUM problem. As this variant is in O(n3/2) time and 3SUM is in O(n2) time, our result gives the first fine-grained equivalence between natural problems of different running times.

Joint work with Andrea Lincoln and Virginia Vassilevska Williams.

27.11.2019 16:15
20.11.2019 16:15
Patryk Mikos
Efficient enumeration of non-isomorphic interval graphs

Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on n vertices with an O(n4) time delay between the output of two consecutive graphs. We improve their algorithm and achieve O(n3 log n) time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all n up to 15 (previous best was 12).

13.11.2019 16:15
Grzegorz Guśpiel
Smaller Universal Targets for Homomorphisms of Edge-Colored Graphs

The density D(G) of a graph G is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class F of graphs, the value D(F) is the supremum of densities of graphs in F.

A k-edge-colored graph is a finite, simple graph with edges labeled by numbers 1,...,k. A function from the vertex set of one k-edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a k-edge-colored graph H (not necessarily with the underlying graph in F) is k-universal for F when any k-edge-colored graph with the underlying graph in F admits a homomorphism to H. Such graphs are known to exist exactly for classes F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a k-uniform graph for a class F is known to be Ω(kD(F)) and O(kd), where d is the ceiling of D(F) (result obtained in 2015 with Gutowski), and has been conjectured to be ϴ(kD(F)).

In this talk, I will present a construction of a k-universal graph on O(kd) vertices for any rational bound d on the density D(F). It follows that if D(F) is rational, the minimum number of vertices in a k-universal graph for F is indeed ϴ(kD(F)).

30.10.2019 16:15
Bartosz Walczak
Coloring and Maximum Weight Independent Set of rectangles

We prove that every intersection graph of axis-parallel rectangles in the plane with clique number ω has chromatic number O(ω log ω), which is the first improvement of the original O(ω2) bound of Asplund and Grünbaum from 1960. As a consequence, we obtain a polynomial-time O(log log n)-approximation algorithm for Maximum Weight Independent Set in axis-parallel rectangles, improving the previous best approximation ratio of O(log n/log log n).

Joint work with Parinya Chalermsook.

23.10.2019 16:15
Gwenaël Joret
Université Libre de Bruxelles
A new proof of the Erdős-Pósa theorem with applications

A classic result of Erdős and Pósa (1965) states that for every graph G and every integer k, either G has k vertex-disjoint cycles, or G has a set of O(k log k) vertices meeting all cycles. The usual way of proving this theorem is through the so-called frame technique. In this talk I will describe another equally simple way of proving the theorem, using a ball packing argument. Then I will describe some applications of this method, including to the variant where only cycles of length at least l are considered.

Joint work with Henning Bruhn, Wouter Cames van Batenburg, and Arthur Ulmer.

16.10.2019 16:15
Mikkel Abrahamsen
Københavns Universitet
Geometric Multicut

We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as Geometric k-Cut, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n4 log3n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2−4/3k)-approximation algorithm.

Joint work with Panos Giannopoulos, Maarten Löffler, and Günter Rote. Presented at ICALP 2019.

19.06.2019 16:15
Bartłomiej Kielak
Generalized Turán densities and counting cycles in graphs

The Turán number ex(n, H) is the maximum number of edges that an H-free graph on n vertices can have. This quantity is well studied for graphs with chromatic number greater than 2, but the problem of determining it for all bipartite graphs remains open. A generalization of the Turán number, namely, the maximum possible number of copies of a graph T in an H-free graph on n vertices, denoted by ex(n, T, H), is recently attracting a lot of attention. In particular, the problem of determining ex(n, C5, C3), posed by Erdős in 1984, was completely solved in the last few years with the use of the flag algebras method.

In this talk, we will show an elementary proof that ex(n, Ck, Ck−2) = (n/k)k + o(nk) for any odd k > 5.

Joint work with Andrzej Grzesik.

12.06.2019 16:15
Bartosz Walczak
Subexponential algorithms for finding large induced sparse subgraphs

Let 𝒞 and 𝒟 be hereditary graph classes. Consider the following problem: given a graph G ∈ 𝒟, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to 𝒞. We prove that it is solvable in 2o(n) time, where n is the number of vertices of G, if the following conditions are satisfied:

  • the graphs in 𝒞 are sparse, i.e., they have linearly many edges in terms of the number of vertices;
  • the graphs in 𝒟 admit balanced separators of size governed by their density, e.g., O(Δ) or O(√m), where Δ and m denote the maximum degree and the number of edges, respectively; and
  • the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph.

This leads, for example, to the following corollaries for specific classes 𝒞 and 𝒟:

  • a largest induced forest in a Pt-free graph can be found in 2Õ(n2/3) time, for every fixed t; and
  • a largest induced planar graph in a string graph can be found in 2Õ(n3/4) time.

Joint work with Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, and Erik Jan van Leeuwen.

15.05.2019 16:15
Krzysztof Kleiner
Range queries and counting triangles

Listing and counting triangles in sparse graphs are well-studied problems. For a graph with m edges, Björklund et al. gave an O(m1.408) algorithm which can list up to m triangles. The exact exponent depends on the exponent omega in matrix multiplication, and becomes 4/3 if omega=2. Pătraşcu proved that an algorithm faster than O(m4/3) would imply a sub-quadratic algorithm for 3-SUM, which is considered unlikely.

In our work we consider a variant of triangle problem asking to determine for every edge the number of triangles which contains that edge. We prove that this problem is no easier than listing up to m triangles, although it still admits an algorithm of the same O(m1.408) complexity. We also propose a natural class of range query problems, including for example the following problem: given a family of ranges in an array, compute the number of inversions in each of them. We prove that all the problems in this class are equivalent, under one-to-polylog reductions, to counting triangles for each edge. In particular the time complexities of these problems are the same up to polylogarithmic factors.

This is joint work of Lech Duraj, Krzysztof Kleiner, Adam Polak and Virginia Vassilevska-Williams.

24.04.2019 16:15
Bartłomiej Bosek
Algorithms for posets and graphs games – coloring and matching

Graph colorings and online algorithms on graphs constitute the key fragments of the algorithmic graph theory. Specifically, the subject of this study will be a presentation of the results concerning

  • different variants of coloring of graphs and partially ordered sets,
  • online coloring of partially ordered sets,
  • incremental matchings of bipartite graphs.

The first part of the talk will concern different aspects of the coloring problem as well as different evidential techniques. The presented results concern majority choosability of digraphs, harmonious coloring of hypergraphs and semi-uni conjecture of product of two posets. The next part of presentation will concern online chain partitioning of posets. There will be presented a full characterization of the class of posets, for which the number of colors (chains) used by first-fit is a function of width, i.e. best offline solution. This part will also present two different subexponential online algorithm for the online chain partitioning problem. The last part will concern the incremental matching problem in bipartite graphs. There will be presented an incremental algorithm that maintains the maximum size matching in total time equal the running time of one of the fastest offline maximum matching algorithm that was given by Hopcroft and Karp. Moreover, I will show an analysis of the shortest augmenting path algorithm.

This is joint work with Marcin Anholcer, Jarosław Grytczuk, Sebastian Czerwiński, Paweł Rzążewski, Stefan Felsner, Kolja Knauer, Grzegorz Matecki, Tomasz Krawczyk, H. A. Kierstead, Matthew Smith, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz.

17.04.2019 16:15
10.04.2019 16:15
Tomasz Krawczyk
Testing isomorphism of circular-arc graphs - Hsu's approach revisited
Circular-arc graphs are intersection graphs of arcs on the circle. The aim of our work is to present a polynomial time algorithm testing whether two circular-arc graphs are isomorphic. To accomplish our task we construct decomposition trees, which are the structures representing all normalized intersection models of circular-arc graphs. Normalized models reflect the neighbourhood relation in a circular-arc graph and can be seen as its canonical representations; in particular, every intersection model can be easily transformed into a normalized one.

Our work adapts and appropriately extends the previous work on similar topic done by Hsu [SIAM J. Comput. 24(3), 411--439, (1995)]. In his work Hsu developed decomposition trees representing the structure of all normalized models of circular-arc graphs. However, due to the counterexample given in [Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013] his decomposition trees can not be used by the algorithm testing isomorphism of circular-arc graphs.
 
06.03.2019 16:15
Zoltán Lóránt Nagy
Eötvös University & Alfréd Rényi Institute of Mathematics
Triangles in line arrangements

A widely investigated subject in combinatorial geometry, originating from Erdős, is the following: given a point set P of cardinality n in the plane, how can we describe the distribution of the determined distances, e.g., determine the maximum number of unit distances, the maximum number of minimum/maximum distances, the minimum number of distinct distances? This has been generalized in many directions by taking point sets in a certain (not necessarily Euclidean) metric space and studying the distribution of certain configurations — and a whole theory emerged.

In this talk I propose the following problem variant: consider planar line arrangements of n lines, and determine the maximum number of unit/maximum/minimum area determined by these lines. We prove that the order of magnitude for the maximum occurrence of unit area lies between n2 and n2+1/4. This result is strongly connected to both additive combinatorial results and Szemerédi-Trotter type results. Next we show a tight bound for the maximum number of minimum area triangles. Finally we discuss a graph theoretic approach for the maximum number of maximum area triangles and present a recursive lower bound.

Joint work with Gábor Damásdi, Leo Martínez-Sandoval and Dániel T. Nagy.

27.02.2019 16:15
Michał Wrona
Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width

We study the amount of consistency (measured by relational width) needed to solve the CSP parametrized by first-order expansions of countably infinite homogeneous graphs, that are, the structures first-order-definable in a homogeneous graph containing the edge relation E, the relation N that holds between different vertices not connected by an edge and the equality. We study our problem for structures that additionally have bounded strict width, i.e., establishing local consistency of an instances of the CSP not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. It is known that with every countably infinite homogeneous graph G the finite unique minimal set S of finite graphs is associated such that some finite H is an induced substructure of G if and only if there is no H' in S such that H' embeds into H.

Our main result is that structures under consideration have relational width exactly (2,L) where L is the maximal size of a forbidden subgraph in S, but not smaller than 3. It implies, in particular, that the CSP parametrized by such structures may be solved in time O(nm) where n is the number of variables and m is the maximum of L and the arities of relations in the signature, while strict width l ensures time O(nl+1). Furthermore, since L may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures, in which case, if finite, relational width is always at most (2,3). 

Finally, we show that certain maximally tractable constraint languages with a first-order definition in a countably infinite homogeneous graph whose CSPs are already known to be solvable in polynomial time by other algorithms may be also solved by establishing consistency. Thus, providing an alternative algorithm for already studied problems.

23.01.2019 16:15
Lech Duraj
A sub-quadratic algorithm for Longest Common Increasing Subsequence

The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated longest common subsequence (LCS). For LCIS, as well as for LCS, there is an O(n2) algorithm and a SETH-based quadratic lower bound. Both the algorithm and the proof of the bound are, however, quite different for LCIS.

For LCS, there is also the Masek-Paterson O(n2/log n) algorithm. Its technique (the 'four Russians trick') does not seem to work for LCIS in any obvious way, so a natural question arises: does any sub-quadratic algorithm exist for Longest Common Increasing Subsequence problem?

We answer this question positively, presenting a O(n2/logan) algorithm for some a>0. The algorithm is not based on memorizing small inputs (often used for logarithmic speedups, including LCS), but rather utilizes a new technique, bounding the number of significant symbol matches between the two sequences.

16.01.2019 16:15
Grzegorz Gutowski
Entropy Compression for Acylic Edge-Colorings

Let G be a graph with maximum degree d. We show a randomized procedure that colors the edges of G so that:

  • every two adjacent edges get two different color;
  • edges of every cycle get at least three different colors.

Such a coloring is called an acylic edge-coloring of G. The minimum number of colors in an acyclic edge coloring of G is called the acylic index of G. It is conjectured that acylic index of G is at most d+2. We are able to prove that our coloring procedure succeeds for roughly 3.97d colors (improving on a previous result that used 4d colors).

This is joint work with Jakub Kozik and Xuding Zhu.

19.12.2018 16:15
Agnieszka Łupińska
University of California, Davis
Gunrock: GPU Graph Analytics

Gunrock is a CUDA library for graph-processing designed specifically for the GPU. It uses a high-level, bulk-synchronous, data-centric abstraction focused on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge.

12.12.2018 16:15
Łukasz Lachowski
Complexity of the quorum intersection property of the Federated Byzantine Agreement System
A Federated Byzantine Agreement System is defined in the paper https://www.stellar.org/papers/stellar-consensus-protocol.pdf
as a pair (V,Q) consisting of a set of nodes V and a quorum function Q : V → P(P(V)) specifying for each node a nonempty family of subsets of nodes, called quorum slices. A subset of nodes is a quorum if and only if for each of its nodes it also contains at least one of its quorum slices. The Disjoint Quorums Problem answers the question whether a given instance of fbas contains two quorums that have no nodes in common. We show that this problem is NP-complete. We also study the problem of finding a quorum of minimal size and show it is NP-hard. Further, we consider the problem of checking whether a given subset of nodes contains a quorum for some selected node. We show this problem is P-complete and describe a method that solves it in linear time with respect to number of nodes and the total size of all quorum slices. Moreover, we analyze the complexity of some of these problems using the parametrized point of view.
 
 
28.11.2018 16:15
05.12.2018 16:15
Piotr Kawałek
Computational approach to solving equations in finite realms

Computational approach to the problem of solving equation, began with the question of David Hilbert. He asked, if there exists an algorithm, that decides wheather given Diophantine equation has a solution or not.  Yuri Matiyasevich proved this problem to be undecidable.  An analogy for decidability in finite realms is tractability. During the talk, we introduce the notion of PolSat problem for finite algebras and discuss the results for the wide class of algebraic structures.

14.11.2018 16:15
21.11.2018 16:15
Michał Seweryn
Bumping a ladder

We show that every 3-connected graph which contains many disjoint 2xn-grid minors, contains a 2x(n+1)-grid-minor. We use this result in a qualitative structure theorem for graphs without large 2xn grids.

This is a result from a joint paper with Tony Huynh, Gwenaël Joret, Piotr Micek and Paul Wollan

17.10.2018 16:15
24.10.2018 16:15
Patryk Mikos
Does the representation matter?

The class of unit interval graphs has at least 3 equivalent definitions:

  • intersection graphs of unit-length intervals,
  • intersection graphs of intervals such that no interval properly contains any other interval,
  • K1,3-free chordal graphs.

We ask whether the competitive ratio in the online unit-interval graph coloring with bandwidths depends on the chosen graph representation.

10.10.2018 16:15
Andrzej Dorobisz
Induced subgraphs of graphs with large chromatic number

Based on the paper
Induced subgraphs of graphs with large chromatic number. III. Long holes
by Maria Chudnovsky, Alex Scott and Paul Seymour

a proof of a 1985 conjecture of Gyarfas that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ

will be presented.

30.05.2018 16:15
06.06.2018 16:15
Grzegorz Herman
Relational parsing: a clean generalized parsing algorithm.

We propose a new, worst-case cubic-time, generalized parsing algorithm for all context-free languages, based on computing the relations between configurations and transitions in a recursive transition network. The algorithm represents such relations using abstract data types, and for their specific (non-canonical) implementations behaves analogously to generalized LL, Left-Corner, or LR. It features a clean mathematical formulation, and can easily be implemented using only immutable data structures.

25.04.2018 16:15
Jacek Krzaczkowski
Complexity of solving equations

Solving equations  is one of the oldest and well known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. If we consider  equations over the ring of integers it is the famous 10th Hilbert Problem on Diophantine Equations, which has been shown to be undecidable. In finite realms such a problem is  obviously decidable in nondeterministic polynomial time.

The talk is intended to present the latest achievements in searching structural algebraic conditions a finite algebra A has to satisfy in order to have a polynomial time algorithm that decides if an equation of polynomials over A has a solution. We will also present the results on  the polynomial  equivalence problem in which we ask whether two polynomials over  a finite algebra describe the same function.

 

This is joint work with Paweł M. Idziak and Piotr Kawałek..

04.04.2018 16:15
Bartosz Walczak
Sparse Kneser graphs are Hamiltonian

For integers k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of {1, …, n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k + 1, k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k ≥ 3, the odd graph K(2k + 1, k) has a Hamilton cycle. Its construction is based on constructing a spanning tree in a suitably defined hypergraph on Dyck words. As a byproduct, it provides an alternative proof of the so-called middle levels theorem, originally proved by Mütze in 2014.

Joint work with Torsten Mütze and Jerri Nummenpalo (arXiv:1711.01636).

28.03.2018 16:15
Grzegorz Guśpiel
On the Complexity of Crossing Minimization
For a bipartite graph G with vertex bipartition (X, Y), a two-layer drawing of G (on the plane) is a placement of vertices in X and Y in distinct points on two parallel lines LX and LY, respectively. Then, each edge is drawn by connecting its end vertices by a straight line segment. A bipartite graph with a two-layer drawing is a two-layered graph. We study basic graph problems on two-layered graphs, where the goal is to minimize the number of pairwise crossing edges in the graph structure we seek. The graph structure can be a perfect matching, a Hamiltonian path or an (s, t)-path. We investigate the complexity of these problems, obtaining some hardness proofs, FPT algorithms and small kernels.
 
This is joint work with Akanksha Agrawal, Jayakrishnan Madathil, Saket Saurabh and Meirav Zehavi.
14.03.2018 16:15
Michael Kompatscher
Charles University in Prague
CSPs of infinite structures and equations in oligomorphic algebras
In 1998 Feder and Vardi famously conjectures that the constraint satisfaction problem (CSP) of a finite structure is either in P or NP-complete. Universal algebra turned out to be the main tool in tackling their conjecture and lead to two recent proofs, showing that CSP(A) is in P if the polymorphism algebra associated with A is a Taylor algebra, and NP-complete otherwise.
For CSPs of structures with infinite domains this universal algebraic approach fails badly in general. However, if the automorphism group of the structure is "sufficiently big", i.e. oligomorphic, many results can be transferred from the finite case. We survey results about the equational structure of oligomorphic algebras and their applications to constraint satisfaction problems.
28.02.2018 16:15
Piotr Micek
Seymour's conjecture on 2-connected graphs of large pathwidth

We prove the conjecture of Seymour (1993) that for every apex-forest H1 and outerplanar graph H2 there is an integer p such that every 2-connected graph of pathwidth at least p contains H1 or H2 as a minor.

This is joint work with Tony Huynh, Gwenaël Joret, and David R.Wood.

17.01.2018 16:15
24.01.2018 16:15
Andrzej Dorobisz
Online bipartite matching with amortized O(log²n) replacements

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O(log²n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n) lower bound.

The previous best known strategy achieved amortized O(√n) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014].

 

Based on the paper:

Online bipartite matching with amortized O(log²n) replacements

by Aaron Bernstein, Jacob Holm and Eva Rotenberg
20.12.2017 16:15
Grzegorz Herman
Declarative name resolution for complex, extensible languages
We present a new, declarative, language-independent model for name resolution, based on a data flow graph built using simple combinators. The model is expressive enough to capture complex name binding rules of modern programming languages (e.g., partial definitions, C++ argument-dependent lookup). It is also designed to make it straightforward toextend a language with new syntactic constructs, including new categories of names. The model, together with a proof-of-concept resolution engine, has been implemented in Haskell, and evaluated on syntax trees of C# programs.
 
(This is joint work with Katarzyna Bułat.)
13.12.2017 16:15
Tony Huynh
Universite de Libre Bruxelles
Strengthening Convex Relaxations of 0/1-Sets using Boolean Formulas

In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points.  On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semi-definite programming hierarchies.  On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization.

We propose a new efficient method that interpolates between these two approaches.  Our procedure strengthens any convex set containing a set of 0/1-points S, by exploiting certain additional information about S.  Namely, the required extra information will be in the form of a Boolean formula defining the target set S.  The strengthened relaxation is obtained by ''feeding'' the convex set into the formula defining S.
As one result, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems.

This is joint work with Samuel Fiorini and Stefan Weltge.

29.11.2017 16:15
Adam Polak
Open problems in algorithms and complexity
During the talk I'll present several interesting open problems, including, but not limited to:
  • Conditional lower bounds for k-mismatch pattern matching
  • Faster algorithms for subset sum
  • Complexity of 3-coloring for graphs with excluded k-paths
22.11.2017 16:15
Patryk Mikos
On-line interval coloring for bounded length intervals

On-line interval coloring was studied by Kierstead and Trotter. They presented an algorithm with competitive ratio 3,and showed a construction which implies that there is no algorithm with competitive ratio strictly less than 3. However, their construction in asymptotic case requires intervals with possibly unbounded length.

We are interested in a variant of the on-line interval coloring problem in which all intervals have lenght between 1 and L. We show that as L tends to infinity the asymptotic competitive ratio tends to 5/2. Moreover we show that for L=1+epsi there is no algorithm with competitive ratio less than 5/3 and for L=2+epsi there is no algotihm with competitive ratio less than 7/4.

Finally, we want to know how the asymptotic competitive ratio changes as a function of L.

15.11.2017 16:15
Tomasz Krawczyk
Representation and coloring of partially ordered sets under conditions of incomplete information

The purpose of my talk is to discuss several problems related to coloring and construction of appropriate representation for partially ordered sets (also posets) and graph classes derived from posets. In these problems, we will assume the following two scenarios:

in the first scenario, an algorithm receives a poset element one after another. For each new element added, the algorithm takes an irrevocable decision (assigns a color or extends a current representation) just after this element is presented (algorithms that work under such conditions are called on-line).

in the second scenario, an algorithm receives an incomparability graph of some poset and a representation of some parts of this graph, and its task is to check whether this partial representation can be extended to a representation of the whole graph that is appropriate for the considered class of graphs.

In the context of on-line algorithms, we focus our attention on two problems: partitioning posets into chains, which is a special case of on-line coloring of incomparability graphs, and embedding posets into d-dimentional space Rd.

In the context of extending partial representations problems, we are interested in graph classes whose representations introduce a natural order on vertices of these graphs.

We focus our attention on:

  • function graphs that are intersection graphs of continuous functions [0,1] R,

  • permutation graphs that are intersection graphs of linear functions [0,1] R,

  • trapezoid graphs that are intersection graphs of trapezoids spanned between two fixed parallel lines containing the bases of these trapezoids.

25.10.2017 16:15
Bartłomiej Bosek
A Tight Bound for Shortest Augmenting Paths on Trees

The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T=(WB, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et. al. that the total length of all shortest augmenting paths found is O(n log n). In this paper we prove a tight O(n log n) upper bound for the total length of shortest augmenting paths for trees improving over O(n log² n) bound.

 

21.06.2017 16:15
Damian Goik
Succinct progress measures for solving parity games

The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasipolynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear. Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right.

Based on the paper:
Succinct progress measures for solving parity games,
by Marcin Jurdziński and Ranko Lazić

 

14.06.2017 16:15
Piotr Wójcik
On the asymptotic density of valid sentences in first-order logic about one binary relation

This study arises from the following question: what is the proportion of tautologies of the given length n among the number of all FO relational sentences of length n? We investigate the simplest language with a fixed signature σ = {r}, where r is a binary relation symbol. The model with four logic symbols and an universal quantifier lead us to discover an unexpected result - the fraction of valid sentences is always greater than a fixed constant and therefore the density, if exists, is positive. The main theorem is derived from the analysis of structural properties of FO formulae, which themselves bear strict resemblance to structural properties of λ-terms.

31.05.2017 16:15
Piotr Micek
Ramsey Theory for Binary Trees and the Separation of Tree-chromatic Number from Path-chromatic Number

We propose a Ramsey theory for binary trees and prove that for every r-coloring of "strong copies" of a small binary tree in a huge complete binary tree T, we can find a strong copy of a large complete binary tree in T with all small copies monochromatic. As an application, we construct a family of graphs which have tree-chromatic number at most 2 while the path-chromatic number is bounded. This construction resolves a problem posed by Seymour.

Joint work with Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros, Heather Smith, Libby Taylor, and Tom Trotter.

10.05.2017 16:15
Torsten Ueckerdt
Karlsruhe Institute of Technology
The k-Strong Induced Arboricity of a Graph

Motivated by a connection to vertex-distinguishing colorings, we initiate the study of a new graph covering parameters: The k-strong induced arboricity. For a graph G and a positive integer k, a k-strong induced forest F in G is an induced forest in which every component has at least k edges. An edge in G is called k-valid if it is contained in at least one k-strong induced forest. The k-strong induced arboricity fk(G) is the smallest number m such that all k-valid edges of G can be covered with m k-strong induced forests in G.

We demonstrate that the k-strong induced arboricity is not monotone, neither in k, nor under taking subgraphs or even induced subgraphs. In particular we construct 2-degenerate graphs G with fk(G)
3 and fk+1(G) arbitrarily large. Focusing on the supremum fk(C) of fk(G) among all graphs G from a given graph class C, we prove that fk(G) is finite whenever C is of bounded expansion. For the class C of planar graphs we prove that fk(C) is 8,9 or 10. Moreover we give necessary and sufficient conditions for f1(C) to be finite in terms of r-shallow minors of graphs in C, a notion recently introduced by Nešetřil and Ossona de Mendez.

This is based on joint work with Maria Axenovich, Philip Dörr, Daniel Gonçalves, and Jonathan Rollin.

26.04.2017 16:15
Marcin Pilipczuk
University of Warsaw
Subexponential Parameterized Algorithms for Planar Graphs, Apex-Minor-Free Graphs and Graphs of Polynomial Growth via Low Treewidth Pattern Covering

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties:

1) A induces a subgraph of G of treewidth O(√k log k), and

2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2O(√k log2k)nO(1))−1, where n is the number of vertices of G.

Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√k log2k)nO(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed k-Path, Weighted k-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. We also provide a similar statement for graph classes of polynomial growth.

In the talk I will first focus on the background and motivation, and then highlight the main ideas of the proof by sketching the proof for the case of graph classes of polynomial growth. Based on joint work with Fedor Fomin, Daniel Lokshtanov, Dániel Marx, Michał Pilipczuk, and Saket Saurabh: http://arxiv.org/abs/1604.05999 and http://arxiv.org/abs/1610.07778.

19.04.2017 16:15
Lech Duraj, Adam Polak
Longest Common Strictly Increasing Subsequecnce

The Longest Common Increasing Subsequence problem is a variant of classic Longest Common Subsequence problem, which can be solved in quadratic time with a simple dynamic programming algorithm. During the talk we will show a reduction from the Orthogonal Vectors problem to the Longest Common Increasing Subsequence problem which proves that the latter cannot be solved in strongly subquadratic time unless the SETH is false.

 

Simple modifications of the reduction prove that the problem for k sequences cannot be solved in O(nk-ε) time, that the same lower bounds apply to the Longest Common Weakly Increasing Subsequence, and that the assumption of SETH can be replaced with a weaker statement about satisfiability of non-deterministic branching programs.

15.03.2017 16:15
Manuel Bodirsky
TU Dresden
The tractability conjecture for finitely bounded homogeneous structures
Finitely bounded homogeneous structures form a large class of infinite structures that can be seen as a generalisation of the class of all finite structures. Many results about finite structures, in particular in the context of the complexity of constraint satisfaction problems, can be generalised to this larger class. In this talk I will present a reformulation of a tractability conjecture for CSPs for this class in terms of polymorphisms, due to Barto and Pinsker (LICS 2016), and I will present a proof that the condition given in the tractability conjecture is decidable (under some Ramsey-theoretic assumptions that might hold in general for all reducts of finitely bounded homogeneous structures).
25.01.2017 16:15
01.03.2017 16:15
Grzegorz Guśpiel
Partial Visibility Representation Extension Problem

We study a class of graphs that have a special geometric representation. By a bar visibility representation of an undirected graph we mean a function that associates with each vertex of a graph a horizontal line segment in such a way, that between segments representing two ends of an edge there is a vertical strip (of visibility). In case of directed graphs, we additionally assume that the visibility is from the bottom to the top, that is the line segment representing the source of the edge is below the one for the target.

Graphs admitting such representations are well understood and can be recognized in linear time, both in the undirected and in the directed case. We work in a more subtle setting, where line segments are already associated with some vertices of a graph, and the question is if this can be extended to a bar visibility representation of an entire graph. We prove some results on complexity of this kind of problems.

This is joint work with Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk and Giuseppe Liotta. The manuscript is available here: https://arxiv.org/abs/1512.00174

18.01.2017 16:15
Marian Mrozek
The discrete charm of Morse theory
The lecture will start with recalling P.S. Alexandroff's Theorem (1937) on mutual equivalence of posets and T0 topologies on finite sets. Next, we will outline the combinatorial version of the classical Morse Theory presented by R. Forman in 1998. Then, we will elaborate Forman's ideas towards the combinatorial topological dynamics with potential applications in Big Data problems and time series. The topics of the lecture will be expanded in a course for PhD students in the summer semester 2016/17.
11.01.2017 16:15
Patryk Mikos
Online coloring of intervals with bandwidth
We study the online interval coloring problem with bandwidth. The input is a sequence of pairs Ji= (Ii,wi) where Ii is an interval on the real line and wi is a real number from (0,1]. In this setting a proper coloring is a function f:Ji →N such that for each color c and any point p on the real line, the sum of bandwidths of intervals containing p and colored by c does not exceed 1. The best known lower bound on the competitive ratio in this problem is 24/7. We present an explicit strategy for Presenter that increases the competitive ratio ifor this problem to at least 4.1626.
21.12.2016 16:15
Maciej Bendkowski
Boltzmann samplers: a framework for random generation of combinatorial structures with an application to lambda calculus
In their seminal paper, Duchon et al. proposed a surprisingly simple, general-purpose framework of Boltzmann samplers meant for random generation of combinatorial structures. In this talk we revisit their method and discuss its elegant relation with analytic combinatorics as well as important practical implementation details. Finally, we discuss the application of Boltzmann samplers to the random generation of lambda terms used, e.g. in testing functional programming compilers.
14.12.2016 16:15
Grzegorz Matecki
Two-Dimensional Irregular Packing Problem
We present results on packing irregular shapes onto given sheets of material.
30.11.2016 18:15
Bartosz Walczak
Coloring curves that cross a fixed curve
A class of graphs is χ-bounded if the chromatic number of all graphs in the class is bounded by some function of their clique number. String graphs are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are χ-bounded. In particular, it is known since 2012 that the class of all string graphs is not χ-bounded. We prove that for every integer t≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is χ-bounded. This result is best possible in several aspects; for example, the upper bound t on the number of crossings with the fixed curve cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in so-called k-quasi-planar topological graphs. This is joint work with Alexandre Rok.
23.11.2016
Piotr Danilewski
Functional Code Building

 
A typical language translator uses a parser to convert an input string into some internal representation, usually in a form of an AST. The AST is then analyzed and transformed in passes. In the final pass, the AST is converted into the output, be it a machine code or source code of another language.
 
However, if we try to combine different languages, e.g. for a purpose of a multi-domain project, we may have a problem: each language uses different kinds of AST nodes, has different assumptions on the AST structure and features different pass algorithms. Settling for the common ground by limiting the node types, assumptions, and algorithms limits how the languages may reason about their code. Any high-level information is lost in such representation and high-level transformations cannot be defined.
 
Working on the common AST is similar to unstructured programming: AST acts as a global machine state. Any change to the state, e.g. introduced by a new language, may inadvertely affect the behavior of the existing languages. In regular programming we have moved away from unstructured programming towards higher abstraction levels, e.g. through functional programming. If it can be done to regular programming, can it be done to AST and code builders as well?
 
Our solution treats AST nodes not as objects of a fixed type. Instead, it is a function with its body describing entirely the behavior of such node. Even the connection between the nodes is represented internally by the function, in a form of continuations. 
The passes over the AST are replaced by a single invocation of these functions. The node functions may contain code for multiple stages of code analysis. In order to reduce the run time these additional stages are scheduled through dynamic staging.
 
This gives the power of abstraction to code building. Even nodes come from different languages may interact, as long as they understand the passed arguments.
 
This major change on how a code is represented requires changes in how we think about common basic operations during language interpretation:
- how do we link two nodes/functions together?
- how do we create control flow structures?
- how do we perform name lookups, even across different languages?
- how do we optimize the code so that the AST layer dissapears when generating code?
- what language-specific optimizations can be performed and how do we specify them?
 
We will address these questions in the upcoming talk.

16.11.2016
Bartłomiej Bosek
Every digraph is majority 4-choosable
A majority coloring of a digraph is a coloring of its vertices such that for each vertex at most half of its out-neighbors has the same color as that vertex. A digraph D is majority k-choosable if for any assignment of color lists of size k to the vertices there is a majority coloring of D from these lists. We prove the statement in the title. This gives a positive answer to a question posed recently in 1. This is a joint work with Marcin Anholcer and Jarosław Grytczuk.
  1. S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen, D. R. Wood, Majority Colourings of Digraphs, Arxiv.
  2. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk Every digraph is majority 4-choosable, Arixv.
09.11.2016
26.10.2016
Adam Polak
Open problems in on-line and approximation algorithms
During the talk I will present several promising open problems including:
  • Online Deadline Scheduling with Machine Augmentation
  • Scheduling with Precedence Constraints
  • Multiway Cut
  • Traveling Repairman Problem
19.10.2016
Bartosz Walczak
Common tangents of two disjoint polygons in linear time and constant workspace
A tangent of a polygon is a line touching but not crossing the polygon. Two disjoint polygons can have four, two, or no common tangents, depending on whether the convex hulls of the polygons are disjoint, overlapping, or nested. We describe a very simple linear-time constant-workspace algorithm to compute all common tangents of two disjoint polygons, each given by a read-only array of its corners in a cyclic order. This is joint work with Mikkel Abrahamsen.
12.10.2016
Adam Polak
Why is it hard to beat O(n^2) for Longest Common Weakly Increasing Subsequecnce?
 
For many years the classic Longest Common Subsequecnce problem (LCS) have not seen any significant improvement over the simple quadratic time dynamic programming algorithm, with the current fastest algorithm by Masek and Paterson dating back to 1980. In the meantime numerous related problems were studied, among them the Longest Common (Weakly) Increasing Subsequecnce problem, for which Yang, Huang, and Chao found a quadratic time dynamic programming algorithm. Despite some attempts, their result have not been improved for over a decade. In a recent line of research Abboud, Backurs, and Vassilevska Williams show a reduction from SAT to LCS, proving that LCS cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis is false. During the talk I will present an analogous hardness result for the Longest Common Increasing Subsequecnce problem.
01.06.2016
Szymon Borak
Polynomial time algorithm for finding Hamiltonian cycles in thin grid graphs

In general, Hamiltonian Cycle Problem is NP-complete in triangular and square grids. In "Not being(super)thin or solid is hard: A study of grid Hamiltonicity" Arkin et al. claimed HCP for thin triangular grids and thin square grids to be NP-complete as well. However the arguments they gave are incorrect. In fact we show that thin triangular grids as well as thin square grids always have HC. Moreover we show a linear algorithm for finding a HC in such graphs.

25.05.2016
Kolja Knauer
Université Aix-Marseille
Orienting triangulations - towards Schynyder woods on orientable surfaces

We show that the edges of any triangulation of a closed surface different from the projective plane and the sphere can be oriented such that every vertex has non-zero outdegree divisble by three. This confirms a conjecture of Barát and Thomassen. We will explain why this is a first step towards the generalization of Schynyder woods from the plane to orientable surfaces and what is know
about this problem.

20.04.2016
Adam Polak
On subposets of dimension two

We study the maximum guaranteed size of a dimension two subposet of an n-element poset. A trivial lower bound of the order of n^{1/2} follows from the Dilworth's theorem. We show an upper bound of the order of n^{2/3} improving the n^{0.8295} result by Reiniger and Yeager. We also discuss promising methods for achieving a better lower bound.

30.03.2016
Michał Śliwka
Teroplan
Efficient algorithm for several diverse results in public transport routing system

We present a solution to problem arising in public transport routing systems:
How to efficiently obtain several diverse transit routes given a single-shortest-path solver together with graph representation of transport network.
The input contains desired number of results, not departure time range length which may be unknown even roughly.
We assume optimisation of both travel time and amount of penalties.

Based on public transport routing engine developed (2012-2013) in Teroplan S.A. (e-podróżnik.pl)

23.03.2016
Damian Goik
Direct solver algorithms for systems created on the basis of adaptive meshes


Solving linear systems of equations is a necessary step in numerical methods such as the Finite Element Method and Finite Difference Method. A variety of algorithms has been developed over the years including direct and indirect methods. In this work I want to present an direct multifrontal solver algorithm for special cases of systems coming from  h-adaptive two and three dimensional meshes. The solver algorithm is expressed through graph grammar productions and takes the advantage of advanced parallelization platform Galois.

based on the paper:

Damian Goika, Konrad Jopeka, Maciej Paszyńskia, Andrew Lenhartha, Donald Nguyenb and Keshav Pingalib,
Graph Grammar based Multi-thread Multi-frontal Direct Solver with Galois Scheduler,
doi:10.1016/j.procs.2014.05.086

10.02.2016
William Trotter
Georgia Institute of Technology
Dimension and Cut Vertices

Motivated by quite recent research involving the relationship between the dimension of a poset and graph theoretic properties of its cover graph, we show that for every $d\ge 1$, if $P$ is a poset and the dimension of a subposet $B$ of $P$ is at most~$d$ whenever the cover graph of $B$ is a block of the cover graph of $P$, then the dimension of $P$ is at most $d+2$.  We also construct examples which show that this inequality is best possible.
We consider the proof of the upper bound to be fairly elegant and relatively compact.  However, we know of no simple proof for the lower bound, and our argument requires a powerful tool known as the Product Ramsey Theorem.  As a consequence, our constructions involve posets of enormous size.

This is joint work with Bartosz Walczak and Ruidong Wang.

27.01.2016
Miron Ficak
On Exact Quantum Query Complexity

We present several families of total boolean functions which have exact quantum query complexity which is a constant multiple (between 1/2 and 2/3) of their classical query complexity, and show that optimal quantum algorithms for these functions cannot be obtained by simply computing parities of pairs of bits. We also characterise the model of nonadaptive exact quantum query complexity in terms
of coding theory and completely characterise the query complexity of symmetric boolean functions in this context. These results were originally inspired by numerically solving the semidefinite programs characterising quantum query complexity for small problem sizes.

Based on the paper:

On Exact Quantum Query Complexity, by Ashley Montanaro, Richard Jozsa and Graeme Mitchison

20.01.2016
Michał Seweryn
Data Structures on Event Graphs

We investigate the behavior of data structures when the input and operations
are generated by an event graph. This model is inspired by Markov chains.
We are given a fixed graph G, whose nodes are annotated with operations of the type insert, delete, and query. The algorithm responds to the requests as it encounters them during a (random or adversarial) walk in G. We study the limit behavior of such a walk and give an efficient algorithm for recognizing which structures can be generated. We also give a near-optimal algorithm for successor searching if the event graph is a cycle and the walk is adversarial. For a random walk, the algorithm becomes optimal.

Based on the paper:

Data Structures on Event Graphs, by Bernard Chazelle and Wolfgang Mulzer

16.12.2015
Michał Kosnowski
Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem

We examine the problem of determining a spanning tree of a given graph
such that the number of internal nodes is maximum. The best approximation algorithm known so far for this problem is due to Prieto and Sloper and has a ratio of 2. For graphs without pendant nodes, Salamon has lowered this factor to 7/4 by means of local search. However, the approximative behaviour of his algorithm on general graphs has remained open. In this paper we show that a simplified and faster version of Salamon's algorithm yields a 5/3-approximation even on general graphs. In addition to this, we investigate a node weighted variant of the problem for which Salamon achieved a ratio of 2·Δ(G)−3. Extending Salamon's approach we obtain a factor of 3+epsi for any epsi>0. We complement our results with worst case instances showing that our analyses are tight.

Based on the paper:

Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem, by Martin Knauer and Joachim Spoerhase

09.12.2015
Konrad Kalita
A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows

A new approach to the minimum-cost integral flow problem for small values of the flow is presented. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(k log(kn) + log2(kn)) time and using 2k(kn)O(1) processors. Thus, in particular, for the minimum-cost flow of value O(log n), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms.

Based on the paper:

A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows, by Andrzej Lingas and Mia Persson

 

18.11.2015
Maciej Poleski
Hitting All Maximal Independent Sets of a Bipartite

We prove that given a bipartite graph G with vertex set V and an integer k,
deciding whether there exists a subset of V of size at most k hitting all maximal independent sets of G is complete for the class Σp2

Based on the paper:

Hitting All Maximal Independent Sets of a Bipartite, by Jean Cardinal and Gwenaël Joret

28.10.2015
Ariel Gabizon
Technion, Israel
Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

A probabilistically checkable proof (PCP) enables, e.g., checking the satisfiability of a 3-SAT formula ɸ, while only examining a constant number of locations in the proof. A long line of research led to the construction of PCPs with length that is quasi-linear in n := |ɸ|.


In a zero knowledge PCP with knowledge bound K, reading any K symbols of the proof reveals no additional information besides the validity of the statement; e.g., no information is revealed about the assignment satisfying ɸ. Kilian, Petrank, and Tardos gave a transformation from any PCP into a ZK-PCP with knowledge bound K, for any desired K. A drawback of their transformation is that it requires multiplying the proof length by a factor of (at least) K^6.


In this work, we show how to construct PCPs that are zero knowledge for knowledge bound K and of length quasilinear in K and n, provided that the prover is forced to write the proof in two rounds. In this model, which we call duplex PCP (DPCP), the verifier gets an oracle string from the prover, then replies with some randomness, and then gets another oracle string from the prover, and it can make up to K queries to both oracles.


Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but rely on algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure (which many constructions have, including [BFLS91,ALMSS98,BS08]) we can add the zero knowledge property at virtually no cost while introducing only minor modifications in the algorithms of the prover and verifier. We believe that our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.


Joint work with Eli Ben-Sasson, Alessandro Chiesa and Madars Virza
21.10.2015
Ariel Gabizon
Technion, Israel
Representative sets for multisets

In this talk I will explain this notion. Then, to illustrate its usefulness, I will show how it was used by Fomin, Lokshtanov and Saurabh to design a fast algorithm for finding long simple paths in a directed graph.

Finally, I will describe a recent work where we generalize the notion of a representative set to a family of multisets and derive algorithmic applications.

 

Based on the paper Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints with Daniel Lokshtanov and Michał Pilipczuk

03.06.2015
Łukasz Lachowski
An Algorithmic Characterization of Polynomial Functions over Z_{p^n}
In this paper we consider polynomial representability of functions defined over Z_{p^n} , where p is a prime and n is a positive integer. Our aim is to provide an algorithmic characterization that (i) answers the decision problem: to determine whether a given function over Z_{p^n} is polynomially representable or not, and (ii) finds the polynomial if it is polynomially representable. The previous characterizations given by Kempner (Trans. Am. Math. Soc. 22(2):240266, 1921) and Carlitz (Acta Arith. 9(1), 6778, 1964) are existential in nature and only lead to an exhaustive search method, i.e. algorithm with complexity exponential in size of the input. Our characterization leads to an algorithm whose running time is linear in size of input. We also extend our result to the multivariate case.  
References:
Ashwin Guha, Ambedkar Dukkipati, An Algorithmic Characterization of Polynomial Functions over Z_{p^n}, Algorithmica (2015) 71:201-218
27.05.2015
Paweł Zegartowski
Cache-Oblivious Hashing
The hash table, especially its external memory version, is one of the most important index structures in large databases. Assuming a truly random hash function, it is known that in a standard external hash table with block size b, searching for a particular key only takes expected average t_q=1+1/2^Ω(b) disk accesses for any load factor α bounded away from 1. However, such near-perfect performance is achieved only when b is known and the hash table is particularly tuned for working with such a blocking. In this paper we study if it is possible to build a cache-oblivious hash table that works well with any blocking. Such a hash table will automatically perform well across all levels of the memory hierarchy and does not need any hardware-specific tuning, an important feature in autonomous databases.

We first show that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves t_q=1+Θ(α/b) even if a truly random hash function is used. Then we demonstrate that the block probing algorithm (Pagh et al. in SIAM Rev. 53(3):547558, 2011) achieves t_q=1+1/2^Ω(b), thus matching the cache-aware bound, if the following two conditions hold: (a) b is a power of 2; and (b) every block starts at a memory address divisible by b. Note that the two conditions hold on a real machine, although they are not stated in the cacheoblivious model. Interestingly, we also show that neither condition is dispensable: if either of them is removed, the best obtainable bound is t_q=1+O(α/b), which is exactly what linear probing achieves.  


References:
Rasmus Pagh, ZheweiWei, Ke Yi, Qin Zhang, Cache-Oblivious Hashing, Algorithmica (2014) 69:864-883
20.05.2015
Łukasz Majcher
List Coloring in the Absence of a Linear Forest
The k-COLORING problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The LIST k-COLORING problem requires in addition that every vertex u must receive a color from some given set L(u)⊆{1,...,k}. Let P_n denote the path on n vertices, and G+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. For any two fixed integers k and r, we show that LIST k-COLORING can be solved in polynomial time for graphs with no induced rP_1+P_5, hereby extending the result of Hoàng, Kami´nski, Lozin, Sawada and Shu for graphs with no induced P_5. Our result is tight; we prove that for any graph H that is a supergraph of P_1 + P_5 with at least 5 edges, already LIST 5-COLORING is NP-complete for graphs with no induced H.  
References:
Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, List Coloring in the Absence of a Linear Forest, Algorithmica (2015) 71:2135
13.05.2015
Krzysztof Kulig
Metrical Service Systems with Multiple Servers
The problem of metrical service systems with multiple servers ((k,l)-MSSMS), proposed by Feuerstein (LATIN'98: Theoretical Informatics, Third Latin American Symposium, 1998), is to service requests, each of which is an l-point subset of a metric space, using k servers in an online manner, minimizing the distance traveled by the servers. We prove that Feuerstein's deterministic algorithm for (k,l)- MSSMS actually achieves an improved competitive ratio of k\cdot({k+l}\choose{l})-1) on uniform metrics.  
References:
Ashish Chiplunkar, Sundar Vishwanathan, Metrical Service Systems with Multiple Servers, Algorithmica (2015) 71:219231
06.05.2015
Maciej Solon
Minimum Fill-in of Sparse Graphs: Kernelization and Approximation
The MINIMUM FILL-IN problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop kernelization algorithms for the problem on several classes of sparse graphs. We obtain linear kernels on planar graphs, and kernels of size O(k^{3/2}) in graphs excluding some fixed graph as a minor and in graphs of bounded degeneracy. As a byproduct of our results, we obtain approximation algorithms with approximation ratios O(log k) on planar graphs and O(√k·log k) on H-minor-free graphs. These results significantly improve the previously known kernelization and approximation results for MINIMUM FILL-IN on sparse graphs.  
References:
Fedor V. Fomin, Geevarghese Philip, Yngve Villanger; Minimum Fill-in of Sparse Graphs: Kernelization and Approximation, Algorithmica (2015) 71:120
29.04.2015
Agnieszka Łupińska
Strong Conflict-Free Coloring for Intervals
We consider the k-strong conflict-free (k-SCF) coloring of a set of points on a line with respect to a family of intervals: Each point on the line must be assigned a color so that the coloring is conflict-free in the following sense: in every interval I of the family there are at least k colors each appearing exactly once in I .We first present a polynomial-time approximation algorithm for the general problem; the algorithm has approximation ratio 2 when k=1 and 5−2/k when k≥2. In the special case of a family that contains all possible intervals on the given set of points, we show that a 2-approximation algorithm exists, for any k≥1. We also provide, in case k=O(polylog(n)), a quasipolynomial time algorithm to decide the existence of a k-SCF coloring that uses at most q colors.  
References:
Panagiotis Cheilaris, Luisa Gargano, Adele A. Rescigno, Shakhar Smorodinsky, Strong Conflict-Free Coloring for Intervals, Algorithmica (2014) 70:732-749
22.04.2015
Marcin Regdos
An O(n^4) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
The bisection problem asks for a partition of the n vertices of a graph into two sets of size at most \ceil{n/2}, so that the number of edges connecting the sets is minimised. A grid graph is a finite connected subgraph of the infinite two-dimensional grid. It is called solid if it has no holes. Papadimitriou and Sideri (Theory Comput Syst 29:97110, 1996) gave an O(n^5) time algorithm to solve the bisection problem on solid grid graphs. We propose a novel approach that exploits structural properties of optimal cuts within a dynamic program. We show that our new technique leads to an O(n^4) time algorithm.  
References:
Andreas Emil Feldmann, Peter Widmayer, An O(n^4) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs, Algorithmica (2015) 71:181-200
15.04.2015
Maciej Bendkowski
Contention Resolution under Selfishness
In many communications settings, such as wired and wireless local-area networks, when multiple users attempt to access a communication channel at the same time, a conflict results and none of the communications are successful. Contention resolution is the study of distributed transmission and retransmission protocols designed to maximize notions of utility such as channel utilization in the face of blocking communications.

An additional issue to be considered in the design of such protocols is that selfish users may have incentive to deviate from the prescribed behavior, if another transmission strategy increases their utility. The work of Fiat et al. (in SODA'07, pp.179188, SIAM, Philadelphia 2007) addresses this issue by constructing an asymptotically optimal incentive-compatible protocol. However, their protocol assumes the cost of any single transmission is zero, and the protocol completely collapses under non-zero transmission costs.

In this paper we treat the case of non-zero transmission cost c.We present asymptotically optimal contention resolution protocols that are robust to selfish users, in two different channel feedback models. Our main result is in the Collision Multiplicity Feedback model, where after each time slot, the number of attempted transmissions is returned as feedback to the users. In this setting, we give a protocol that has expected cost Θ(n+c·log n) and is in o(1)-equilibrium, where n is the number of users.  


References:
George Christodoulou, Katrina Ligett, Evangelia Pyrga, Contention Resolution under Selfishness, Algorithmica (2014) 70:675693
08.04.2015
01.04.2015,Patryk Mikos
Randomized Online Graph Coloring
 
25.03.2015
Lech Duraj, Grzegorz Gutowski, Jakub Kozik
Chip games and paintability
We present a natural family of chip games with strong ties to paintability, on-line 2-coloring of hypergraphs and Maker-Braker games. We solve some of those games and as a result we obtain interesting results in aforementioned areas. One of those results is that the difference between paintabilty and choosability of a graph can be arbitrarily large.
 
18.03.2015
Jarosław Duda
Asymmetric Numeral Systems: adding fractional bits to Huffman coder
Entropy coding is an integral part of most data compression systems. There were previously used mainly two approaches: Huffman coding which is fast but approximates probabilities with powers of 1/2 (suboptimal compression ratio), and arithmetic coding which uses nearly accurate probabilities at cost of being an order of magnitude slower (more expensive). I will talk about new approach: Asymmetric Numeral Systems (ANS), which while using nearly accurate probabilities, has turned out to allow for even faster implementations than Huffman coding. Consequently, succeeding compressors have already switched to ANS in recent months.  
11.03.2015
Piotr Danilewski Universität des Saarlandes
AnyDSL - a host for any language
In a multi-domain project, there is no single programming language that can be used to program everything. Instead, a combination of general-purpose and domain-specific languages (DSLs) are used. Unfortunately, many domains lack a good, representative DSL, due to domain diversity and difficulty of creating a new compiler. Moreover, the communication across the languages is limited, often requiring the data to be serialized, and reducing the quality of optimization and compile-time verification.

In our talk we present our approach to solve these problems, by introducing a new metamorphic language - AnyDSL. The parsing and execution of AnyDSL can be interleaved and the latter can influence the former - e.g. by introducing a new grammar with which parsing should resume. Regardless of the language the source is written in, all code is translated into a low-level, functional representation in continuous passing style (AIR). AIR serves as a "meeting point", permitting inter-DSL communication. AIR can be interpreted or compiled to LLVM bytecode and then to machine code.

New grammars are defined also within AnyDSL. Unlike typical parser generators, grammar productions and actions are given as functions. AIR supports dynamic staging - a flexible way to define partial evaluation strategies. With it the overhead of having multiple layers of languages can be resolved early. It also allows the DSL designer to specify domain specific optimizations. After all those transformations, AIR can be compiled to machine code that is efficient, with performance comparable to programs written in general-purpose languages.

In our talk we present a new metamorphic language - AnyDSL. AnyDSL permits the native parser to be exchanged with a custom DSL. Regardless of the DSL however, all code is translated into a low-level, functional representation in continuous passing style (AIR).

New grammars are defined also within AnyDSL, but unlike typical parser generators, grammar productions and actions are given as functions. AIR supports dynamic staging - a flexible way to define partial evaluation strategies to resolve overheads and define domain specific optimizations. AIR can be compiled to machine code, and produced programs have performance comparable to those produced by general-purpose languages.  

04.03.2015

CANCELLED
 
28.01.2015
Michał Zając
Improved Explicit Data Structures in the Bitprobe Model
Buhrman et al. [SICOMP 2002] studied the membership problem in the bitprobe model, presenting both randomized and deterministic schemes for storing a set of size n from a universe of size m such that membership queries on the set can be answered using t bit probes. Since then, there have been several papers focusing on deterministic schemes, especially for the first non-trivial case when n=2. The most recent, due to Radhakrishnan, Shah, and Shannigrahi [ESA 2010], describes non-explicit schemes (existential results) for t≥3 using probabilistic arguments. We describe a fully explicit scheme for n=2 that matches their space bound of Θ(m^{2/5}) bits for t=3 and, furthermore, improves upon it for t>3, answering their open problem. Our structure (consisting of query and storage algorithms) manipulates blocks of bits of the query element in a novel way that may be of independent interest. We also describe recursive schemes for n≥3 that improve upon all previous fully explicit schemes for a wide range of parameters.  
References:
Moshe Lewenstein, J. Ian Munro, Patrick K. Nicholson and Venkatesh Raman, Improved Explicit Data Structures in the Bitprobe Model, ESA 2014, LNCS 8737, pp. 630–641, 2014
21.01.2015
Andrzej Głuszyński
Data Structures for Storing Small Sets in the Bitprobe Model
We study the following set membership problem in the bit probe model: given a set S from a finite universe U, represent it in memory so that membership queries of the form "Is x in S?" can be answered with a small number of bitprobes. We obtain explicit schemes that come close to the information theoretic lower bound of Buhrman et al. [STOC 2000, SICOMP 2002] and improve the results of Radhakrishnan et al. [ESA 2001] when the size of sets and the number of probes is small.

We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Ω(m^{4/7}). The previous best lower bound (shown by Buhrman et al. using information theoretic arguments) was Ω(√m). The same lower bound applies for larger sets using standard padding arguments. This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes.

We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Ω(√m) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets.  


References:
Jaikumar Radhakrishnan, Smit Shah and Saswata Shannigrahi, Data Structures for Storing Small Sets in the Bitprobe Model, ESA 2010, Part II, LNCS 6347, pp. 159–170, 2010.
14.01.2015
Andrzej Dorobisz
Scheduling parallel jobs to minimize the makespan
We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen.

List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.  


References:
Johannes Berit, Scheduling parallel jobs to minimize the makespan, J of Schedulling, 9(2006), 433–452
07.01.2015
Łukasz Kapica
On an on-line scheduling problem for parallel jobs
The non-preemptive on-line scheduling of parallel jobs is addressed. In particular we assume that the release dates and the processing times of the jobs are unknown. It is already known that for this problem Garey and Graham's list scheduling algorithm achieves the competitive factor 2−1/m for the makespan if m identical machines are available and if each job requires only a single machine for processing. Here, we show that the same factor also holds in the case of parallel jobs.  
References:
Edwin Naroska, Uwe Schwiegelshohn, On an on-line scheduling problem for parallel jobs, Information Processing Letters, 81(2002), 297–304.
17.12.2014
Bartosz Wlaczak
Minors and dimension
Streib and Trotter proved in 2012 that posets with bounded height and with planar cover graphs have bounded dimension. Later, Joret et al. proved that the dimension is bounded for posets with bounded height whose cover graphs have bounded tree-width. Recently, I proved that posets of bounded height whose cover graphs exclude a fixed (topological) minor have bounded dimension. This generalizes both the aforementioned results and verifies a conjecture of Joret et al. In this talk, I will introduce the problems of bounding the dimension of posets with sparse cover graphs and the main structural theorems used in the proof of the latter result: the Robertson-Seymour and Grohe-Marx structural decomposition theorems. I will also briefly describe the idea of the proof.  
10.12.2014
26.11.2014,Tomasz Kołodziejski
Opaque sets or how to find a pipe
We'll tackle the problem of finding the smallest set in a given class that meets every line intersecting a given convex set. Such a set is know as a barrier. Particularly interesting barrier classes are: connected sets, poly-lines and arbitrary segment barriers. The algorithmic approach yields various approximation constants around 1.6. Little is known about the exact barriers even for simple figures. Algorithms and proofs will be presented most of which require only basic planar geometry knowledge will little calculus (Cauchy surface area formula will be presented with no proof).  
19.11.2014
Adam Gągol
Very new results on graph sharing games
 
12.11.2014
29.10.2014,Adam Polak
On treewidth parametrization of nonpreemptive multicoloring problem
In the multicoloring problem we are given a graph in which every vertex has some nonnegative integer demand. We have to assign to each vertex a set of colors of the size of the demand of this vertex, in such a way that the sets of any two neighboring vertices are disjoint. In the nonpreemptive version of the problem each set of colors has to be an interval of the natural numbers. The goal is either to minimize the sum of the assigned colors, or to minimize the number of different colors used. In this talk we will discuss the fixed parameter tractability of both these problems when parametrized by the treewidth of the input graph and the maximum demand, the treewidth and the number of different demands, and the treewidth itself.  
22.10.2014
Grzegorz Gutowski
Open Problem Session
A few interesting and promising open problems, including, but not limited to:
* Coloring triangle-free graphs,
* Complexity of graph classes defined by forbidden ordered subgraphs,
* Reconstructing random strings from random substrings,
* Scheduling multiprocessor jobs,
* Storing small sets in just a few bits,
* Colorful homomorphisms of planar graphs,
* Domination games.  
11.06.2014
Radosław Smyrek
Shortest Path Problems on a Polyhedral Surface (by Atlas F. Cook IV, CarolaWenk)
We describe algorithms to compute edge sequences, a shortest path map, and the Fréchet distance for a convex polyhedral surface. Distances on the surface are measured by the length of a Euclidean shortest path. We describe how the star unfolding changes as a source point slides continuously along an edge of the convex polyhedral surface. We describe alternative algorithms to the edge sequence algorithm of Agarwal et al. (SIAM J. Comput. 26(6):1689–1713, 1997) for a convex polyhedral surface. Our approach uses persistent trees, star unfoldings, and kinetic Voronoi diagrams. We also show that the core of the star unfolding can overlap itself when the polyhedral surface is non-convex.  
References:
Atlas F. Cook IV, CarolaWenk, Shortest Path Problems on a Polyhedral Surface, Algorithmica (2014) 69:58–77
04.06.2014
Gabriel Fortin
On Cutwidth Parameterized by Vertex Cover (by Marek Cygan et al.)
We study the CUTWIDTH problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for CUTWIDTH with running time O(2^k n^O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2^{n/2}n^O(1)) time algorithm for CUTWIDTH on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for CUTWIDTH on a graph class where the problem remains NP-complete. Additionally, we show that CUTWIDTH parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP ⊆ coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both TREEWIDTH and PATHWIDTH parameterized by vertex cover do admit polynomial kernels.  
References:
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, On Cutwidth Parameterized by Vertex Cover, Algorithmica (2014) 68:940–953
28.05.2014
Krzysztof Pasek
Online Square Packing with Gravity (by S.P.Fekete, T.Kamphans, N.Schweer)
We analyze the problem of packing squares in an online fashion: Given a semi-infinite strip of width 1 and an unknown sequence of squares of side length in [0, 1] that arrive from above, one at a time. The objective is to pack these items as they arrive, minimizing the resulting height. Just like in the classical game of Tetris, each square must be moved along a collision-free path to its final destination. In addition, we account for gravity in both motion (squares must never move up) and position (any final destination must be supported from below). A similar problem has been considered before; the best previous result is by Azar and Epstein, who gave a 4-competitive algorithm in a setting without gravity (i.e., with the possibility of letting squares "hang in the air") based on ideas of shelf packing: Squares are assigned to different horizontal levels, allowing an analysis that is reminiscent of some binpacking arguments. We apply a geometric analysis to establish a competitive factor of 3.5 for the bottom-left heuristic and present a 34/13≈2.6154-competitive algorithm.  
References:
Sándor P. Fekete, Tom Kamphans, Nils Schweer, Online Square Packing with Gravity, Algorithmica (2014) 68:1019–1044
21.05.2014
Szymon Borak
Competitive-reachability for special classes of graphs
The reachability r(D) of a directed graph D is the number of ordered pairs of distinct vertices (x, y) with a directed path from x to y. Two players maximizer and minimizer play the following game on graph G. They orient the edges of G alternately until all edges of G have been oriented. The maximizer attempts to maximize the reachability, while the minimizer attempts to minimize the reachability, of the resulting digraph. If both players play optimally, then the reachability is fixed. Competitive-reachability is a value of reachability for the optimal play on graph G. We determine the competitive-reachability for outerplanar graphs and some other special classes of graphs.  
14.05.2014
Grzegorz Gutowski, Jakub Kozik
Lower bound for on-line graph coloring of bipartite graphs
In this talk we propose a strategy for Presenter in on-line graph coloring game. The strategy constructs bipartite graphs and forces any on-line coloring algorithm to use 2 log n - 10 colors, where n is the number of vertices in the constructed graph. This is best possible up to an additive constant.  
References:
http://arxiv.org/abs/1404.7259
16.04.2014
Arkadiusz Olek
Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem, (by M.Knauer, J.Spoerhase)
We examine the problem of determining a spanning tree of a given graph such that the number of internal nodes is maximum. The best approximation algorithm known so far for this problem is due to Prieto and Sloper and has a ratio of 2. For graphs without pendant nodes, Salamon has lowered this factor to 7/4 by means of local search. However, the approximative behaviour of his algorithm on general graphs has remained open. In this paper we show that a simplified and faster version of Salamon's algorithm yields a 5/3-approximation even on general graphs. In addition to this, we investigate a node weighted variant of the problem for which Salamon achieved a ratio of 2·Δ(G)−3. Extending Salamon's approach we obtain a factor of 3+ε for any ε>0. We complement our results with worst case instances showing that our analyses are tight.  
References:
Martin Knauer, Joachim Spoerhase, Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem, Algorithmica, DOI 10.1007/s00453-013-9827-7
09.04.2014
Adam Polak
A Generalization of the Convex Kakeya Problem, (by Ahn et al.)
Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kakeya's problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Θ(n log n)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G.  
References:
Hee-Kap Ahn, SangWon Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama, Antoine Vigneron, A Generalization of the Convex Kakeya Problem, Algorithmica, DOI 10.1007/s00453-013-9831-y
26.03.2014
Jakub Adamek
A Universal Randomized Packet Scheduling Algorithm (by Łukasz Jeż)
We give a memoryless scale-invariant randomized algorithm REMIX for Packet Scheduling that is e/(e−1)-competitive against an adaptive adversary. REMIX unifies most of previously known randomized algorithms, and its general analysis yields improved performance guarantees for several restricted variants, including the s-bounded instances. In particular, REMIX attains the optimum competitive ratio of 4/3 on 2-bounded instances.

Our results are applicable to a more general problem, called Item Collection, in which only the relative order between packets' deadlines is known. REMIX is the optimal memoryless randomized algorithm against adaptive adversary for that problem  


References:
Łukasz Jeż, A Universal Randomized Packet Scheduling Algorithm, Algorithmica (2013) 67:498–515, DOI 10.1007/s00453-012-9700-0
19.03.2014
cancelled
SeminariumIT 19.03.2014
 
12.03.2014
Michał Dyrek
Balanced Partitions of Trees and Applications (by A.E.Feldmann, L.Foschini)
We study the problem of finding the minimum number of edges that, when cut, form a partition of the vertices into k sets of equal size. This is called the k-BALANCED PARTITIONING problem. The problem is known to be inapproximable within any finite factor on general graphs, while little is known about restricted graph classes.

We show that the k-BALANCED PARTITIONING problem remains APX-hard even when restricted to unweighted tree instances with constant maximum degree. If instead the diameter of the tree is constant we prove that the problem is NP-hard to approximate within n^c, for any constant c<1.

If vertex sets are allowed to deviate from being equal-sized by a factor of at most 1+ε, we show that solutions can be computed on weighted trees with cut cost no worse than the minimum attainable when requiring equal-sized sets. This result is then extended to general graphs via decompositions into trees and improves the previously best approximation ratio from O(log^{3/2}(n)/ε^2) [Andreev and Räcke in Theory Comput. Syst. 39(6):929–939, 2006] to O(log n). This also settles the open problem of whether an algorithm exists for which the number of edges cut is independent of ε.  


References:
Andreas Emil Feldmann, Luca Foschini, Balanced Partitions of Trees and Applications, Algorithmica DOI 10.1007/s00453-013-9802-3
05.03.2014
26.02.2014,Adam Gągol
Natural proofs (by A. Razborov, S. Rudich)
The notion of natural proof is introduced. We argue that the known proofs of lower bounds on the complexity of explicit Boolean functions in nonmonotone models fall within our definition of natural. We show, based on a hardness assumption, that natural proofs can not prove superpolynomial lower bounds for general circuits. Without the hardness assumption, we are able to show that they can not prove exponential lower bounds (for general circuits) for the discrete logarithm problem. We show that the weaker class of AC^0-natural proofs which is sufficient to prove the parity lower bounds of Furst, Saxe, and Sipser, Yao, and Hastad is inherently incapable of proving the bounds of Razborov and Smolensky. We give some formal evidence that natural proofs are indeed natural by showing that every formal complexity measure, which can prove superpolynomial lower bounds for a single function, can do so for almost all functions, which is one of the two requirements of a natural proof in our sense.  
References:
Alexander A. Razborov, Steven Rudich, Natural proofs, Journal of Computer and System Sciences, 55(1997), 24-35
22.01.2014
Maciej Solon
Scheduling with an Orthogonal Resource Constraint
We address a scheduling problem that arises in highly parallelized environments like modern multi-core CPU/GPU computer architectures where simultaneously active jobs share a common limited resource, e.g., memory cache. The scheduler must ensure that the demand for the common resource never exceeds the available capacity. This introduces an orthogonal constraint to the classical minimum makespan scheduling problem. Such a constraint also arises in other contexts where a common resource is shared across machines. We study the non-preemptive case of this problem and present a (2+\epsi)-approximation algorithm which relies on the interplay of several classical and modern techniques in scheduling like grouping, job-classification, and the use of configuration-LPs. This improves upon previous bound of 3 that can be obtained by list scheduling approaches, and gets close to the (3/2−\epsi)-inapproximability bound. If the number of machines or the number of different resource requirements are bounded by a constant we obtain a polynomial time approximation scheme.  
References:
Martin Niemeier, Andreas Wiese, Scheduling with an Orthogonal Resource Constraint, Algorithmica, DOI 10.1007/s00453-013-9829-5
15.01.2014
Michał Sapalski
Linear-Time Algorithms for Tree Root Problems
Let T be a tree on a set V of nodes. The p-th power T^p of T is the graph on V such that any two nodes u and w of V are adjacent in T^p if and only if the distance of u and w in T is at most p. Given an n-node m-edge graph G and a positive integer p, the p-th tree root problem asks for a tree T , if any, such that G = T^p. Given an n-node m-edge graph G, the tree root problem asks for a positive integer p and a tree T , if any, such that G = T^p. Kearney and Corneil gave the best previously known algorithms for both problems. Their algorithm for the former (respectively, latter) problem runs in O(n^3) (respectively, O(n^4)) time. In this paper, we give O(n+m)-time algorithms for both problems.  
References:
Maw-Shang Chang, Ming-Tat Ko, Hsueh-I Lu, Linear-Time Algorithms for Tree Root Problems, Algorithmica, DOI 10.1007/s00453-013-9815-y
08.01.2014
Andrzej Dorobisz
Linear Recognition and Embedding of Fibonacci Cubes
Fibonacci strings are binary strings that contain no two consecutive 1s. The Fibonacci cube Γ_h is the subgraph of the h-cube induced by the Fibonacci strings. These graphs are applicable as interconnection networks and in theoretical chemistry, and lead to the Fibonacci dimension of a graph. We derive a new characterization of Fibonacci cubes. The characterization is the basis for an algorithm which recognizes these graphs in linear time. Moreover, a graph which was recognized as a Fibonacci cube can be embedded into a hypercube using Fibonacci strings within the same time bound.  
References:
Aleksander Vesel, Linear Recognition and Embedding of Fibonacci Cubes, Algorithmica, DOI 10.1007/s00453-013-9839-3
18.12.2013
Bartłomiej Ryniec
Preprocess, Set, Query!
Thorup and Zwick (J.ACM 52(1):1–24, 2005 and STOC'01) in their seminal work introduced the notion of distance oracles. Given an n-vertex weighted undirected graph with m edges, they show that for any integer k ≥ 1 it is possible to preprocess the graph in O˜(m n^{1/k}) time and generate a compact data structure of size O(k n^{1+1/k}). For each pair of vertices, it is then possible to retrieve an estimated distance with multiplicative stretch 2k−1 in O(k) time. For k=2 this gives an oracle of O(n^{1.5}) size that produces in constant time estimated distances with stretch 3.
Recently, Patrascu and Roditty (In: Proc. of 51st FOCS, 2010) broke the theoretical status-quo in the field of distance oracles and obtained a distance oracle for sparse unweighted graphs of O(n^{5/3}) size that produces in constant time estimated distances with stretch 2.
In this paper we show that it is possible to break the stretch 2 barrier at the price of non-constant query time in unweighted undirected graphs.We present a data structure that produces estimated distances with 1+ε stretch. The size of the data structure is O(n m^{1−ε'}) and the query time is O˜(m^{1−ε'}). Using it for sparse unweighted graphs we can get a data structure of size O(n^{1.87}) that can supply in O(n^{0.87}) time estimated distances with multiplicative stretch 1.75.  
References:
Ely Porat, Liam Roditty, Preprocess, Set, Query! Algorithmica (2013) 67:516–528
11.12.2013
Agnieszka Dymel
Online Coloring of Bipartite Graphs with and without Advice
In the online version of the well-known graph coloring problem, the vertices appear one after the other together with the edges to the already known vertices and have to be irrevocably colored immediately after their appearance. We consider this problem on bipartite, i.e., two-colorable graphs. We prove that at least \floor{1.13746·log_2(n) − 0.49887} colors are necessary for any deterministic online algorithm to be able to color any given bipartite graph on n vertices, thus improving on the previously known lower bound of \floor{log_2(n)}+1 for sufficiently large n.
Recently, the advice complexity was introduced as a method for a fine-grained analysis of the hardness of online problems. We apply this method to the online coloring problem and prove (almost) tight linear upper and lower bounds on the advice complexity of coloring a bipartite graph online optimally or using 3 colors. Moreover, we prove that O(√n) advice bits are sufficient for coloring any bipartite graph on n vertices with at most \ceil{log_2(n)} colors.  
References:
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic, Lucia Keller, Online Coloring of Bipartite Graphs with and without Advice Algorithmica, DOI 10.1007/s00453-013-9819-7
04.12.2013
Sebastian Syta
Online Unweighted Knapsack Problem with Removal Cost
We study the online unweighted knapsack problem with removal cost. The input is a sequence of items u_1,u_2,...,u_n, each of which has a size and a value, where the value of each item is assumed to be equal to the size. Given the ith item u_i, we either put u_i into the knapsack or reject it with no cost. When u_i is put into the knapsack, some items in the knapsack are removed with removal cost if the sum of the size of u_i and the total size in the current knapsack exceeds the capacity of the knapsack. Here the removal cost means a cancellation charge or disposal fee. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack minus the total removal cost occurred.
We consider two kinds of removal cost: unit and proportional cost. For both models, we provide their competitive ratios. Namely, we construct optimal online algorithms and prove that they are best possible.  
References:
Xin Han, Yasushi Kawase, Kazuhisa Makino, Online Unweighted Knapsack Problem with Removal Cost, Algorithmica DOI 10.1007/s00453-013-9822-z
27.11.2013
Michał Bejda
Data Structures on Event Graphs
We investigate the behavior of data structures when the input and operations are generated by an event graph. This model is inspired by Markov chains. We are given a fixed graph G, whose nodes are annotated with operations of the type insert, delete, and query. The algorithm responds to the requests as it encounters them during a (random or adversarial) walk in G. We study the limit behavior of such a walk and give an efficient algorithm for recognizing which structures can be generated. We also give a near-optimal algorithm for successor searching if the event graph is a cycle and the walk is adversarial. For a random walk, the algorithm becomes optimal.  
References:
Bernard Chazelle, Wolfgang Mulzer, Data Structures on Event Graphs, Algorithmica DOI 10.1007/s00453-013-9838-4
20.11.2013
Damian Krolik
Parameterized Analysis of Paging and List Update Algorithms
It is well-established that input sequences for paging and list update have locality of reference. In this paper we analyze the performance of algorithms for these problems in terms of the amount of locality in the input sequence. We define a measure for locality that is based on Denning's working set model and express the performance of well known algorithms in terms of this parameter. This explicitly introduces parameterized-style analysis to online algorithms. The idea is that rather than normalizing the performance of an online algorithm by an (optimal) offline algorithm, we explicitly express the behavior of the algorithm in terms of two more natural parameters: the size of the cache and Denning's working set measure. This technique creates a performance hierarchy of paging algorithms which better reflects their experimentally observed relative strengths. It also reflects the intuition that a larger cache leads to a better performance. We also apply the parameterized analysis framework to list update and show that certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results.  
References:
Reza Dorrigiv, Martin R. Ehmsen, Alejandro López-Ortiz, Parameterized Analysis of Paging and List Update Algorithms, Algorithmica, DOI 10.1007/s00453-013-9800-5
13.11.2013
Maciej Bendkowski
Analyses of Cardinal Auctions
We study cardinal auctions for selling multiple copies of a good, in which bidders specify not only their bid or how much they are ready to pay for the good, but also a cardinality constraint on the number of copies that will be sold via the auction. We perform first known Price of Anarchy type analyses with detailed comparison of the classical Vickrey-Clarke-Groves (VCG) auction and one based on minimum pay property (MPP) which is similar to Generalized Second Price auction commonly used in sponsored search. Without cardinality constraints, MPP has the same efficiency (total value to bidders) and at least as much revenue (total income to the auctioneer) as VCG; this also holds for certain other generalizations of MPP (e.g., prefix constrained auctions, as we show here). In contrast, our main results are that, with cardinality constraints,
(a) equilibrium efficiency of MPP is 1/2 of that of VCG and this factor is tight,
(b) in equilibrium MPP may collect as little as 1/2 the revenue of VCG.  
References:
Mangesh Gupte, Darja Krushevskaja, S. Muthukrishnan, Analyses of Cardinal Auctions, Algorithmica DOI 10.1007/s00453-013-9832-x
06.11.2013
Karol Różycki
Oblivious Algorithms for the Maximum Directed Cut Problem
We introduce a special family of randomized algorithms for Max DICUT that we call oblivious algorithms. Let the bias of a vertex be the ratio between the total weight of its outgoing edges and the total weight of all its edges. An oblivious algorithm selects at random in which side of the cut to place a vertex v, with probability that only depends on the bias of v, independently of other vertices. The reader may observe that the algorithm that ignores the bias and chooses each side with probability 1/2 has an approximation ratio of 1/4, whereas no oblivious algorithm can have an approximation ratio better than 1/2 (with an even directed cycle serving as a negative example). We attempt to characterize the best approximation ratio achievable by oblivious algorithms, and present results that are nearly tight. The paper also discusses natural extensions of the notion of oblivious algorithms, and extensions to the more general problem of Max 2-AND.  
References:
Uriel Feige, Shlomo Jozeph, Oblivious Algorithms for the Maximum Directed Cut Problem, Algorithmica DOI 10.1007/s00453-013-9806-z
30.10.2013
Igor Adamski
Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2^w nodes under the unit-cost RAM model with a fixed word size w. It is based on the idea of partitioning T into a set of linked small tries, each of which can be maintained efficiently. Our method is not only space-efficient, but also allows the longest common prefix between any query pattern P and the strings currently stored in T to be computed in o(|P|) time for small alphabets, and allows any leaf to be inserted into or deleted from T in o(log|T|) time. To demonstrate the usefulness of our new data structure, we apply it to LZ-compression. Significantly, we obtain the first algorithm for generating the LZ78 encoding of a given string of length n over an alphabet of size σ in sublinear (o(n)) time and sublinear (o(n log σ) bits) working space for small alphabets
(σ = 2^{o(log n \cdot \frac{log log log n}{(log log n)^2})).
Moreover, the working space for our new algorithm is asymptotically less than or equal to the space for storing the output compressed text, regardless of the alphabet size.  
References:
Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung, Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space, Algorithmica DOI 10.1007/s00453-013-9836-6
23.10.2013
Wojciech Łopata
An Algorithmic Characterization of Polynomial Functions over Z_{p^n}
We consider polynomial representability of functions defined over Z_{p^n}, where p is a prime and n is a positive integer. Our aim is to provide an algorithmic characterization that
(i) answers the decision problem: to determine whether a given function over Z_{p^n} is polynomially representable or not,
(ii) finds the polynomial if it is polynomially representable.
The previous characterizations given by Kempner (Trans. Am. Math. Soc. 22(2):240–266, 1921) and Carlitz (Acta Arith. 9(1), 67–78, 1964) are existential in nature and only lead to an exhaustive search method, i.e. algorithm with complexity exponential in size of the input. Our characterization leads to an algorithm whose running time is linear in size of input. We also extend our result to the multivariate case.  
References:
Ashwin Guha, Ambedkar Dukkipati, An Algorithmic Characterization of Polynomial Functions over Z_{p^n},
Algorithmica DOI 10.1007/s00453-013-9799-7
16.10.2013
Jerzy MarcinkowskiUniversity of Wrocław
Finite Controllability and Bounded Derivation Depth
FC (Finite controllability) and BDD (the Bounded Derivation Depth property) are two properties of Datalog/TGD programs.

BDD is equivalent to Positive First Order rewritability -- the very useful property that allows us to use (all the optimizations of) DBMS in order to compute the certain answers to queries in the presence of a theory.

Finite Controllability of a theory T means that if the certain answer to a query Q, for a database instance D , in the presence of T is 'no' then this 'no' is never a result of an unnatural assumption that the counterexample can be infinite.

We conjecture that for any theory T the property BDD implies FC. We prove this conjecture for the case of binary signatures.  


References:
Tomasz Gogacz, Jerzy Marcinkowski: On the BDD/FC conjecture. Proceedings of PODS 2013 (the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems)
14.10.2013
W. Hugh WoodinUC Berkeley
The Continuum Hypothesis and the search for Mathematical Infinitynew place and date: Oct 14, 2013, 16:00,Polska Akademia Umiejętności, Kraków, Sławkowska 17
By middle of the 20th century the problem of the Continuum Hypothesis was widely regarded as one of the prominent problems in all of Mathematics. Remarkably, this question cannot be solved on the basis of the basic principles (these are the ZFC axioms) on which the entire subject is based. This discovery of Cohen, 50 years ago this summer, is arguably one of the major discoveries in the history of modern Mathematics.

But does this mean that the question of the Continuum Hypothesis has no answer? Any "solution" must involve the adoption of new principles but which principles should one adopt? Alternatively, perhaps the correct assessment of Cohen's discovery is that the entire enterprise of the mathematical study of Infinity is ultimately doomed because the entire subject is simply a human fiction without any true foundation. In this case, any "solution" to the Continuum Hypothesis is just an arbitrary (human) choice.

Over the last few years a scenario has emerged by which with the addition of a single new principle not only can the problem of the Continuum Hypothesis be resolved, but so can all of the other problems  which Cohen's method has been used to show are also unsolvable (and there have been many such problems).  Moreover the extension of the basic (ZFC) principles by this new principle would be seen as an absolutely compelling option based on the fundamental intuitions on which the entire mathematical conception of Infinity is founded.

However, this scenario critically depends upon the outcome of a single conjecture. If this conjecture is false then the entire approach, which is the culmination of nearly 50 years of research, fails or at the very least  has to be significantly revised.

Thus the mathematical study of Infinity has arguably reached a tipping point. But which way will it tip?  

09.10.2013

cancelled/moved to 14 X 2013
 
19.06.2013
Jean CardinalUniversité Libre de Bruxelles
On Universal Point Sets for Planar Graphs and Related Problems
A set S of points in the plane is said to be n-universal if every planar graph on n vertices has a straight-line plane embedding on a subset of S. Finding the minimum size f(n) of an n-universal point set is a long-standing open problem, and the current upper and lower bounds differ by a linear factor. We will consider a lower bound technique that allowed us to prove that there is no n-universal point set of size n for any n>14. We will also describe recent results on families of planar graphs on n vertices that cannot be embedded on a common n-point set. This is a joint work with Michael Hoffmann and Vincent Kusters.  
12.06.2013
Marcin Ziemiński
DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs
With the ubiquity of large-scale graph data in a variety of application domains, querying them effectively is a challenge. In particular, reachability queries are becoming increasingly important, especially for containment, subsumption, and connectivity checks. Whereas many methods have been proposed for static graph reachability, many real-world graphs are constantly evolving, which calls for dynamic indexing. In this paper, we present a fully dynamic reachability index over dynamic graphs. Our method, called DAGGER, is a light-weight index based on interval labeling, that scales to million node graphs and beyond. Our extensive experimental evaluation on real-world and synthetic graphs confirms its effectiveness over baseline methods.  
References:
Hilmi Yildirim, Vineet Chaoji, Mohammed J.Zaki, DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs, arXiv:1301.0977
05.06.2013
Patryk Zaryjewski
In-situ associative permuting
The technique of in-situ associative permuting is introduced which is an association of in-situ permuting and in-situ inverting. It is suitable for associatively permutable permutations of {1,2,...,n} where the elements that will be inverted are negative and stored in order relative to each other according to their absolute values. Let K[1...n] be an array of n integer keys each in the range [1,n], and it is allowed to modify the keys in the range [-n,n]. If the integer keys are rearranged such that one of each distinct key having the value i is moved to the i'th position of K, then the resulting arrangement (will be denoted by K^P) can be transformed in-situ into associatively permutable permutation pi^P using only logn additional bits. The associatively permutable permutation pi^P not only stores the ranks of the keys of K^P but also uniquely represents K^P. Restoring the keys from pi^P is not considered. However, in-situ associative permuting pi^P in O(n) time using logn additional bits rearranges the elements of pi^P in order, as well as lets to restore the keys of K^P in O(n) further time using the inverses of the negative ranks. This means that an array of n integer keys each in the range [1,n] can be sorted using only logn bits of additional space.  
References:
A. Emre Cetin, In-situ associative permuting, arXiv:1301.2046
22.05.2013
Przemysław Derengowski
Proper Interval Vertex Deletion
The NP-complete problem PROPER INTERVAL VERTEX DELETION is to decide whether an input graph on n vertices and m edges can be turned into a proper interval graph by deleting at most k vertices. Van Bevern et al. (In: Proceedings WG 2010. Lecture notes in computer science, vol. 410, pp.232–243, 2010) showed that this problem can be solved in O((14k+14)^{k+1}kn^6) time. We improve this result by presenting an O(6^kkn^6) time algorithm for PROPER INTERVAL VERTEX DELETION. Our fixed-parameter algorithm is based on a new structural result stating that every connected component of a {claw, net, tent, C_4, C_5, C_6}-free graph is a proper circular arc graph, combined with a simple greedy algorithm that solves PROPER INTERVAL VERTEX DELETION on {claw, net, tent, C_4, C_5, C_6}-free graphs in O(n+m) time. Our approach also yields a polynomial-time 6-approximation algorithm for the optimization variant of PROPER INTERVAL VERTEX DELETION.  
References:
Pim van't Hof, Yngve Villanger, Proper Interval Vertex Deletion, Algorithmica, DOI 10.1007/s00453-012-9661-3
15.05.2013
Paweł Komosa
Multicut viewed through the eyes of vertex cover
 
References:
Jianer Chen, Jiahao Fany, Iyad A. Kanjz, Yang Liux, Fenghui Zhang, Multicut viewed through the eyes of vertex cover
08.05.2013
Sebastian Syta
A Sublinear Time Algorithm for PageRank Computations
In a network, identifying all vertices whose PageRank is more than a given threshold value $\Delta$ is a basic problem that has arisen in Web and social network analyses. In this paper, we develop a nearly optimal, sublinear time, randomized algorithm for a close variant of this problem. When given a directed network \graph, a threshold value $\Delta$, and a positive constant $c>3$, with probability $1-o(1)$, our algorithm will return a subset $S\subseteq V$ with the property that $S$ contains all vertices of PageRank at least $\Delta$ and no vertex with PageRank less than $\Delta/c$. The running time of our algorithm is always $\tilde{O}(\frac{n}{\Delta})$. In addition, our algorithm can be efficiently implemented in various network access models including the Jump and Crawl query model recently studied by \cite{brautbar_kearns10}, making it suitable for dealing with large social and information networks. As part of our analysis, we show that any algorithm for solving this problem must have expected time complexity of ${\Omega}(\frac{n}{\Delta})$. Thus, our algorithm is optimal up to logarithmic factors. Our algorithm (for identifying vertices with significant PageRank) applies a multi-scale sampling scheme that uses a fast personalized PageRank estimator as its main subroutine. For that, we develop a new local randomized algorithm for approximating personalized PageRank which is more robust than the earlier ones developed by Jeh and Widom \cite{JehW03} and by Andersen, Chung, and Lang \cite{AndersenCL06}.  
References:
Christian Borgs, Michael Brautbar, Jennifer Chayes1, and Shang-Hua Teng, A Sublinear Time Algorithm for PageRank Computations,
24.04.2013
Agnieszka Dymel
A Simple 3-Edge-Connected Component Algorithm
A simple linear-time algorithm for finding all the 3-edge-connected components of an undirected graph is presented. The algorithm performs only one depth-first search over the given graph. Previously best known algorithms perform multiple depth-first searches in multiple phases.  
References:
Yung H.Tsin, A Simple 3-Edge-Connected Component Algorithm, Theory Comput. Systems 40(2007), 125-142
17.04.2013
Tomasz Kołodziejski
8/5 Approximation for TSP Paths
We prove the approximation ratio 8/5 for the metric s-t-Path-TSP problem, and more generally for shortest connected T-joins. The algorithm that achieves this ratio is the simple ``Best of Many'' version of Christofides' algorithm (1976), suggested by An, Kleinberg and Shmoys (2012), which consists in determining the best Christofides s-t-tour out of those constructed from a family Fscr_{>0} of trees having a convex combination dominated by an optimal solution x^* of the fractional relaxation. They give the approximation guarantee sqrt{5}+1/2 for such an s-t--tour, which is the first improvement after the 5/3 guarantee of Hoogeveen's Christofides type algorithm (1991). Cheriyan, Friggstad and Gao (2012) extended this result to a 13/8-approximation of shortest connected T-joins, for |T|≥4.

The ratio 8/5 is proved by simplifying and improving the approach of An, Kleinberg and Shmoys that consists in completing x^*/2 in order to dominate the cost of "parity correction" for spanning trees. We partition the edge-set of each spanning tree in Fscr_{>0} into an s-t--path (or more generally, into a T-join) and its complement, which induces a decomposition of x^*. This decomposition can be refined and then efficiently used to complete x^*/2 without using linear programming or particular properties of T, but by adding to each cut deficient for x^*/2 an individually tailored explicitly given vector, inherent in the problem.

A simple example shows that the Best of Many Christofides algorithm may not find a shorter s-t--tour than 3/2 times the incidentally common optima of the problem and of its fractional relaxation.  


References:
András Sebö, Eight-Fifth Approximation for TSP Paths, Integer Programming and Combinatorial Optimization, LNCS7801, 2013, pp 362-374
10.04.2013
Szymon Borak
On dominating sets of maximal outerplanar graphs
A dominating set of a graph is a set S of vertices such that every vertex in the graph is either in S or is adjacent to a vertex in S. The domination number of a graph G, denoted gamma(G), is the minimum cardinality of a dominating set of G. We show that if G is an n-vertex maximal outerplanar graph, then gamma(G)≤(n+t)/4, where t is the number of vertices of degree 2 in G. We show that this bound is tight for all t≥2. Upper-bounds for gamma(G) are known for a few classes of graphs.  
References:
C.N.Campos and Y.Wakabayashi, On dominating sets of maximal outerplanar graphs, Discrete Appl.Math. 161(2013), 330-335
03.04.2013
Aneta Pawłowska
A Randomized O(log^2 k)-Competitive Algorithm for Metric Bipartite Matching
We consider the online metric matching problem in which we are given a metric space, k of whose points are designated as servers. Over time, up to k requests arrive at an arbitrary subset of points in the metric space, and each request must be matched to a server immediately upon arrival, subject to the constraint that at most one request is matched to any particular server. Matching decisions are irrevocable and the goal is to minimize the sum of distances between the requests and their matched servers.

We give an O(log^2 k)-competitive randomized algorithm for the online metric matching problem. This improves upon the best known guarantee of O(log^3 k) on the competitive factor due to Meyerson, Nanavati and Poplawski (SODA'06). It is known that for this problem no deterministic algorithm can have a competitive better than 2k−1, and that no randomized algorithm can have a competitive ratio better than ln k.  


References:
Nikhil Bansal, Niv Buchbinder, Anupam Gupta, Joseph (Seffi) Naor, A Randomized O(log^2 k)-Competitive Algorithm for Metric Bipartite Matching, Algorithmica, DOI 10.1007/s00453-012-9676-9
27.03.2013
Michał Sapalski
A Lower Bound of 1+ϕ for Truthful Scheduling Mechanisms
We study the mechanism design version of the unrelated machines scheduling problem, which is at the core of Algorithmic Game Theory and was first proposed and studied in a seminal paper of Nisan and Ronen. We give an improved lower bound of 1+ϕ≈2.618 on the pproximation ratio of deterministic truthful mechanisms for the makespan. The proof is based on a recursive preprocessing argument which yields a strictly increasing series of new lower bounds for each fixed number of machines n≥4.  
References:
Elias Koutsoupias, Angelina Vidali, A Lower Bound of 1+ϕ for Truthful Scheduling Mechanisms, Algorithmica, DOI 10.1007/s00453-012-9634-6
13.03.2013
Grzegorz Gutowski,Jakub Kozik
Tic-tac-toe and beyond....
 
23.01.2013
Michał Feret
Relative Convex Hulls in Semi-Dynamic Arrangements
We present a data structure for maintaining the geodesic hull of a set of points (sites) in the presence of pairwise noncrossing line segments (barriers) that subdivide a bounding box into simply connected faces. For m barriers and n sites, our data structure has O((m+n)log(n)) size. It supports a mixed sequence of O(m) barrier insertions and O(n) site deletions in O((m+n)polylog(mn)) total time, and answers analogues of standard convex hull queries in O(polylog(mn)) time.
Our data structure supports a generalization of the sweep line technique, in which the sweep wavefront is a simple closed polygonal curve, and it sweeps a set of n points in the plane by simple moves. We reduce the total time of supporting m online moves of a polygonal wavefront sweep algorithm from the naïve O(m√n polylog(n)) to O((m+n)polylog(mn)).  
References:
Mashhood Ishaque, Csaba D. Tóth, Relative Convex Hulls in Semi-Dynamic Arrangements, Algorithmica DOI 10.1007/s00453-012-9679-6
16.01.2013
Jacek Szmigiel
An Optimal Lower Bound for Buffer Management in Multi-Queue Switches
In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, their excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput.
We present a tight lower bound of e/(e−1) ≈ 1.582 on the competitive ratio of the throughput maximization, which holds even for fractional or randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm RANDOM SCHEDULE. Our result contradicts the claimed performance of the algorithm RANDOM PERMUTATION; we point out a flaw in its original analysis.  
References:
Marcin Bieńkowski, An Optimal Lower Bound for Buffer Management in Multi-Queue Switches, Algorithmica DOI 10.1007/s00453-012-9677-8
09.01.2013
Jakub Adamek
A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem
We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the facilities and the demands of the clients are uniform. The goal is to open a subset of the input points as facilities such that the accumulated cost for the whole point set, consisting of the opening costs for the facilities and the connection costs for the clients, is minimized.
We present a randomized distributed algorithm that computes in expectation an O(1)-approximate solution to the metric facility location problem described above. Our algorithm works in a synchronous message passing model, where each point is an autonomous computational entity that has its own local memory and that communicates with the other entities by message passing.We assume that each entity knows the distance to all the other entities, but does not know any of the other pairwise distances. Our algorithm uses three rounds of all-to-all communication with message sizes bounded to O(log(n)) bits, where n is the number of input points.
We extend our distributed algorithm to constant powers of metric spaces. For a metric exponent l≥1, we obtain a randomized O(1)-approximation algorithm that uses three rounds of all-to-all communication with message sizes bounded to O(log(n)) bits.  
References:
Joachim Gehweiler, Christiane Lammersen, Christian Sohler, A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem, Algorithmica DOI 10.1007/s00453-012-9690-y
19.12.2012
Radoslaw Smyrek
Recognizing d-Interval Graphs and d-Track Interval Graphs
A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-track interval graphs, and (2,..., 2) d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit d-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.  
References:
Minghui Jiang: Recognizing d-Interval Graphs and d-Track Interval Graphs, Algorithmica DOI 10.1007/s00453-012-9651-5
12.12.2012
Jarosław Bielenin
Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines
We design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines, with the same processing time on either machine. (This is a special case of so-called restricted assignment, where the set of eligible machines can be arbitrary for each job.) This is the first improvement of the approximation ratio 2 of Lenstra, Shmoys, and Tardos (Math. Program. 46:259–271, 1990), to a smaller constant for any special case with unbounded number of machines and unbounded processing times.We conclude by showing integrality gaps of several relaxations of related problems.  
References:
Tomáš Ebenlendr, Marek Krˇcál, Jiˇrí Sgall: Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines, Algorithmica DOI 10.1007/s00453-012-9668-9
05.12.2012
Michał Masłowski
On the Exact Complexity of Evaluating Quantified k-CNF
We relate the exponential complexities 2^{s(k)n} of k-SAT and the exponential complexity 2^{s(EVAL(Π_2 3-CNF))n} of EVAL(Π_2 3-CNF) (the problem of evaluating quantified formulas of the form ∀x∃yF(x,y) where F is a 3-CNF in x-variables and y-variables) and show that s(∞) (the limit of s(k) as k→∞) is at most s(EVAL(Π_2 3-CNF)). Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for EVAL(Π_2 3-CNF) running in time 2^{cn} with c<1.
On the other hand, a nontrivial exponential-time algorithm for EVAL(Π_2 3-CNF) would provide a k-SAT solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of the evaluation problem EVAL(Π_2 3-CNF) have nontrivial algorithms, and provide strong evidence that the hardest cases of EVAL(Π_2 3-CNF) must have a mixture of clauses of two types: one universally quantified literal and two existentially quantified literals, or only existentially quantified literals. Moreover, the hardest cases must have at least n−o(n) universally quantified variables, and hence only o(n) existentially quantified variables. Our proofs involve the construction of efficient minimally unsatisfiable k-CNFs and the application of the Sparsification lemma.  
References:
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi, On the Exact Complexity of Evaluating Quantified k-CNF, Algorithmica DOI 10.1007/s00453-012-9648-0
28.11.2012
Agnieszka Łupińska
Speed Scaling on Parallel Processors
In this paper we investigate dynamic speed scaling, a technique to reduce energy consumption in variable-speed microprocessors. While prior research has focused mostly on single processor environments, in this paper we investigate multiprocessor settings. We study the basic problem of scheduling a set of jobs, each specified by a release date, a deadline and a processing volume, on variable-speed processors so as to minimize the total energy consumption.

We first settle the problem complexity if unit size jobs have to be scheduled. More specifically, we devise a polynomial time algorithm for jobs with agreeable deadlines and prove NP-hardness results if jobs have arbitrary deadlines. For the latter setting we also develop a polynomial time algorithm achieving a constant factor approximation guarantee. Additionally, we study problem settings where jobs have arbitrary processing requirements and, again, develop constant factor approximation algorithms. We finally transform our offline algorithms into constant competitive online strategies.  


References:
Susanne Albers, Fabian Müller, Swen Schmelzer, Speed Scaling on Parallel Processors, Algorithmica DOI 10.1007/s00453-012-9678-7
21.11.2012
Gabriel Fortin
3-Colouring AT-Free Graphs in Polynomial Time
Determining the complexity of the colouring problem on AT-free graphs is one of long-standing open problems in algorithmic graph theory. One of the reasons behind this is that AT-free graphs are not necessarily perfect unlike many popular subclasses of AT-free graphs such as interval graphs or co-comparability graphs. In this paper, we resolve the smallest open case of this problem, and present the first polynomial time algorithm for the 3-colouring problem on AT-free graphs.  
References:
Juraj Stacho, 3-Colouring AT-Free Graphs in Polynomial Time , Algorithmica (2012) 64:384–399
14.11.2012
Łukasz Janiszewski
The Complexity of the Empire Colouring Problem
We investigate the computational complexity of the empire colouring problem (as defined by Percy Heawood in Q. J. Pure Appl. Math. 24:332–338, 1890) for maps containing empires formed by exactly r>1 countries each. We prove that the problem can be solved in polynomial time using s colours on maps whose underlying adjacency graph has no induced subgraph of average degree larger than s/r. However, if s≥3, the problem is NP-hard even if the graph is a forests of paths of arbitrary lengths (for any r≥2, provided s<2r−\sqrt{2r+1/4}+3/2. Furthermore we obtain a complete characterization of the problem's complexity for the case when the input graph is a tree, whereas our result for arbitrary planar graphs fall just short of a similar dichotomy. Specifically, we prove that the empire colouring problem is NP-hard for trees, for any r≥2, if 3≤s≤2r−1 (and polynomial time solvable otherwise). For arbitrary planar graphs we prove NP-hardness if s<7 for r=2, and s<6r−3, for r≥3. The result for planar graphs also proves the NP-hardness of colouring with less than 7 colours graphs of thickness two and less than 6r−3 colours graphs of thickness r≥3.  
References:
Andrew R.A. McGrae, Michele Zito, The Complexity of the Empire Colouring Problem, Algorithmica DOI 10.1007/s00453-012-9680-0
07.11.2012
Maciej Bendkowski
Sex-Equal Stable Matchings: Complexity and Exact Algorithms
We explore the complexity and exact computation of a variant of the classical stable marriage problem in which we seek matchings that are not only stable, but are also "fair" in a formal sense. In particular, we study the sex-equal stable marriage problem (SESM), in which, roughly speaking, we wish to find a stable matching with the property that the men's happiness is as close as possible to the women's happiness. This problem is known to be strongly NP-hard  
References:
Eric McDermid, Robert W. Irving, Sex-Equal Stable Matchings: Complexity and Exact Algorithms, Algorithmica, DOI 10.1007/s00453-012-9672-0
31.10.2012
Tomasz JurkiewiczMax Planck Institute for Informatics, Saarbrücken
The Cost of Address Translation
Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. We address the problem of the computational cost of address translation in virtual memory. Starting point for our work is the observation that the analysis of some simple algorithms (random scan of an array, binary search, heapsort) in either the RAM model or the EM model (external memory model) does not correctly predict growth rates of actual running times. We propose the VAT model (virtual address translation) to account for the cost of address translations and analyze the algorithms mentioned above and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms.  
References:
Tomasz Jurkiewicz and Kurt Mehlhorn, The Cost of Address Translation, ALENEX, January 2013.
24.10.2012
Adam Polak
Algorithms for Placing Monitors in a Flow Network
 
References:
Francis Chin, Marek Chrobak, Li Yan, Algorithms for Placing Monitors in a Flow Network
17.10.2012
Lech Duraj
A linear algorithm for 3-letter LCWIS problem
The problem of finding longest weakly increasing common subsequence (LCWIS) of two sequences is a variant of popular longest common subsequence (LCS) problem. While there are no known methods to find LCS in truly sub-quadratic time, there are faster algorithms to compute LCWIS if the alphabet size is small enough. We present a linear-time algorithm finding LCWIS over 3-letter alphabet. Up to now, the fastest known algorithm was O(min{m + n log n, m log log m}).  
10.10.2012
Ariel GabizonTechnion
Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors
Kuznetsov and Tsybakov considered the problem of storing information in a memory where a certain p-fraction of the n cells are `stuck' at certain values. The person writing in the memory - the `encoder'- knows which cells are stuck, and to what values. The person who will read the memory later - the `decoder' is required to retrieve the message encoded *without* the information about which cells are stuck.

Kuznetsov and Tsybakov showed there are schemes where a message of length (1-p-o(1))*n can be encoded. We give the first such explicit schemes.

Our schemes follow from a construction of an object called an `invertible zero-error disperser'.

Joint work with Ronen Shaltiel.

 

20.06.2012
Szymon Borak
Monadic Second Order Logic on Graphs with Local Cardinality Constraints
We show that all problems of the following form can be solved in polynomial time for graphs of bounded treewidth: Given a graph G and for each vertex v of G a set α(v) of non-negative integers. Is there a set S of vertices or edges of G such that S satisfies a fixed property expressible in monadic second order logic, and for each vertex v of G the number of vertices/edges in S adjacent/incident with v belongs to the set α(v)? A wide range of problems can be formulated in this way, for example Lovasz's General Factor Problem.  
References:
Stefan Szeider, Monadic Second Order Logic on Graphs with Local Cardinality Constraints, LNCS 5162, pp. 601–612, 2008.
13.06.2012
Marek Markiewicz
Sharp Separation and Applications to Exact and Parameterized Algorithms
Many divide-and-conquer algorithms employ the fact that the vertex set of a graph of bounded treewidth can be separated in two roughly balanced subsets by removing a small subset of vertices, referred to as a separator. In this paper we prove a trade-off between the size of the separator and the sharpness with which we can fix the size of the two sides of the partition. Our result appears to be a handy and powerful tool for the design of exact and parameterized algorithms for NP-hard problems. We illustrate that by presenting two applications.  
References:
Fedor V. Fomin, Fabrizio Grandoni, Daniel Lokshtanov and Saket Saurabh, Sharp Separation and Applications to Exact and Parameterized Algorithms, Algorithmica, DOI 10.1007/s00453-011-9555-9
06.06.2012
30.05.2012,Andrzej Pezarski
On-line clique covering of unit interval graphs
We consider an on-line version of the minimal clique covering problem. We focus on a class of unit interval graphs and their different representations.

It is known that all greedy algorithms solving this roblems use at least two times more cliques in the worst scenario than it is necessary in the optimal off-line solution. We introduce non-greedy approach, which leads us to construction of new better algorithms.

We start with connected graphs presented in a connected way with their proper interval representations. For this case we show an algorithm using at worst 8/5 times more cliques than it is needed. Later, we generalize this solution to the case of non-connected graphs. This time, we obtain an algorithm using at worst 13/8 times more cliques than it is necessary. We also generalize both algorithms to work without interval representation. Finally, we move towards unit interval representation and present an algorithm using at most 8/5 times more cliques than needed.

The performance of the algorithms is the best possible.

 

23.05.2012
Maciej Wawro
Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming
The NP-hard general factor problem asks, given a graph and for each vertex a list of integers, whether the graph has a spanning subgraph where each vertex has a degree that belongs to its assigned list. The problem remains NP-hard even if the given graph is bipartite with partition U+V, and each vertex in U is assigned the list {1}; this subproblem appears in the context of constraint programming as the consistency problem for the extended global cardinality constraint.

We show that this subproblem is fixed-parameter tractable when parameterized by the size of the second partite set V. More generally, we show that the general factor problem for bipartite graphs, parameterized by |V|, is fixed-parameter tractable as long as all vertices in U are assigned lists of length 1, but becomes W[1]-hard if vertices in U are assigned lists of length at most 2. We establish fixed-parameter tractability by reducing the problem instance to a bounded number of acyclic instances, each of which can be solved in polynomial time by dynamic programming.  


References:
Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider and Anders Yeo, Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming, Algorithmica, DOI 10.1007/s00453-011-9548-8
16.05.2012
Kasper Kopeć
Minimum Weight Cycles and Triangles: Equivalences and Algorithms
We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirected n-node graph with edge weights in {1,...,M} or in a directed n-node graph with edge weights in {-M,..., M} and no negative cycles can be efficiently reduced to finding a minimum weight triangle in an Theta(n)-node undirected graph with weights in {1,...,O(M)}. Roughly speaking, our reductions imply the following surprising phenomenon: a minimum cycle with an arbitrary number of weighted edges can be "encoded" using only three edges within roughly the same weight interval! This resolves a longstanding open problem posed by Itai and Rodeh [SIAM J. Computing 1978 and STOC'77].
A direct consequence of our efficient reductions are O (Mn^{omega})-time algorithms using fast matrix multiplication (FMM) for finding a minimum weight cycle in both undirected graphs with integral weights from the interval [1,M] and directed graphs with integral weights from the interval [-M,M]. The latter seems to reveal a strong separation between the all pairs shortest paths (APSP) problem and the minimum weight cycle problem in directed graphs as the fastest known APSP algorithm has a running time of O(M^{0.681}n^{2.575}) by Zwick [J. ACM 2002].
> In contrast, when only combinatorial algorithms are allowed (that is, without FMM) the only known solution to minimum weight cycle is by computing APSP. Interestingly, any separation between the two problems in this case would be an amazing breakthrough as by a recent paper by Vassilevska W. and Williams [FOCS'10], any O(n^{3-eps})-time algorithm (eps>0) for minimum weight cycle immediately implies a O(n^{3-delta})-time algorithm (delta>0) for APSP.
 
References:
Liam Roditty and Virginia Vassilevska Williams, Minimum Weight Cycles and Triangles: Equivalences and Algorithms, http://arxiv.org/abs/1104.2882v1
09.05.2012
Maciej Gawron
An exact algorithm for the Maximum Leaf Spanning Tree problem
Given an undirected graph with n vertices, the Maximum Leaf Spanning Tree problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4^k poly(n)) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008). Daligault et al. (2010) improved the branching and obtained a running time of O(3.72^k poly(n)). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the Connected Dominating Set problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Ω(2^n) barrier and proposed an O(1.9407^n)-time algorithm (Fomin et al. 2008). Based on some useful properties of Kneis et al. (2008) and Daligault et al. (2010), we present a branching algorithm whose running time of O(1.8966^n) has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Ω(1.4422^n) for the worst case running time of our algorithm.  
References:
Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith, An exact algorithm for the Maximum Leaf Spanning Tree problem, Theoretical Computer Science 412(2011) 6290–6302
25.04.2012
Gwenaël Joret
Sorting under Partial Information (without the Ellipsoid Algorithm)
We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. In this talk, we describe a simple and efficient algorithm for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithm differs in essential ways from theirs: Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed in a restricted class of graphs, permitting the use of a simpler algorithm. Furthermore, we compute or approximate the entropy at most twice, instead of doing it at each iteration.

Joint work with J. Cardinal, S. Fiorini, R. M. Jungers, and J. I. Munro.  
18.04.2012
Bartosz Szabucki
Fast Minor Testing in Planar Graphs
Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is an edge of H, then there is an edge of G between components C_u and C_v. A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time O(2^O(h)·n+n^2·log n) a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming.  
References:
Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau and Dimitrios M. Thilikos, Fast Minor Testing in Planar Graphs, Algorithmica, DOI 10.1007/s00453-011-9563-9
11.04.2012
Robert Obryk
Wait-free parallel summing snapshot
Atomic snapshot[1] is a well known parallel data structure that implements two operations: update which updates a thread's value and scan which returns an array of all threads' values. A wait-free implementation of this structure using O(1) time for update and O(n) time for scan in O(n) memory is known[2]. In this talk we will present an implementation of a similar structure, where scan returns not the whole array, but its sum (or the result of applying any other associative operation to its elements). The structure uses O(n) memory, update runs in O(log n) time and scan runs in O(1) time. We will also present an implementation of a structure, which has an atomic update-and-scan operation. Its memory complexity is O(n log^2 n), and time complexity of the operation is O(log^2 n). We will show how to implement that structure on machines with small word size without sacrificing wait-freeness nor complexity.  
References:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.3090&rep=rep1&type=pdf
http://groups.csail.mit.edu/tds/papers/Shavit/RST.pdf
04.04.2012
Piotr Wójcik
Algorithmic Meta-theorems for Restrictions of Treewidth
``Possibly the most famous algorithmic meta-theorem is Courcelle's theorem, which states that all MSO-expressible graph properties are decidable in linear time for graphs of bounded treewidth. Unfortunately, the running time's dependence on the formula describing the problem is in general a tower of exponentials of unbounded height, and there exist lower bounds proving that this cannot be improved even if we restrict ourselves to deciding FO logic on trees.

We investigate whether this parameter dependence can be improved by focusing on two proper subclasses of the class of bounded treewidth graphs: graphs of bounded vertex cover and graphs of bounded max-leaf number.We prove stronger algorithmic meta-theorems for these more restricted classes of graphs.More specifically, we show it is possible to decide any FO property in both of these classes with a singly exponential parameter dependence and that it is possible to decide MSO logic on graphs of bounded vertex cover with a doubly exponential parameter dependence. We also prove lower bound results which show that our upper bounds cannot be improved significantly, under widely believed complexity assumptions. Our work addresses an open problem posed by Michael Fellows.''  


References:
Michael Lampis, Algorithmic Meta-theorems for Restrictions of Treewidth, Algorithmica, DOI 10.1007/s00453-011-9554-x
21.03.2012
Mikołaj Bojańczyk, UW
Automata Theory in XML
I will describe how finite automata are used in XML documents. The main idea is that an XML document is a finite tree, and therefore one can use tree automata to process XML documents. XML documents bring new questions that have not been previously studied by automata theory. Maybe the most interesting issue is that when modeling an XML document as a tree, the node labels come from an infinite alphabet. For instance, a node that stores a book in a bibliographic database comes with the book's ID. A typical query might check if the database contains two books with the same ID.  
14.03.2012
Bartłomiej Bosek,Grzegorz Matecki
News on Semiantichains and Unichain Coverings
The famous Dilworth's Theorem states that for any partial order the size of a largest antichain is equal to the size of a smallest chain covering. In the late '70s C.Greene and D.Kleitman successfully generalized Dilworth's Theorem which moved forward the studies of partially ordered sets. Later, Saks proved equivalent statement that in the product CxQ of a chain C and an arbitrary poset Q the size of maximum antichain equals the size of minimum chain covering with chains of the form {c}xC' and Cx{q} (called unichains). We study Saks-West's conjecture which gives a nice generalization of the previous theorem:

For any two posets P and Q the size of a maximum semiantichain and the size of minimum unichain covering in the product PxQ are equal.

Here, semiantichain means a set for which each two points are not in a common unichain. B.Bosek, S.Felsner, K.Knauer and G.Matecki found conditions on P and Q that imply the conjecture in case of several new classes of posets. However, they also found an example showing that in general this min-max relation is false. This finally disproofs 30 year old conjecture of M.Saks and D.West.
 

07.03.2012
Kamil Kraszewski
New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications
A pair of unit clauses is called conflicting if it is of the form (x), (¯x). A CNF formula is unit-conflict free (UCF) if it contains no pair of conflicting unit clauses. Lieberherr and Specker (J. ACM 28:411–421, 1981) showed that for each UCF CNF formula with m clauses we can simultaneously satisfy at least ϕ'm clauses, where ϕ'=(√5−1)/2. We improve the Lieberherr-Specker bound by showing that for each UCF CNF formula F with m clauses we can find, in polynomial time, a subformula F' with m' clauses such that we can simultaneously satisfy at least ϕ'm+(1−ϕ')m'+(2−3ϕ')n"/2 clauses (in F), where n"cis the number of variables in F which are not in F'.We consider two parameterized versions of MAX-SAT, where the parameter is the number of satisfied clauses above the bounds m/2 and m(√5−1)/2. The former bound is tight for general formulas, and the later is tight for UCF formulas. Mahajan and Raman (J. Algorithms 31:335–354, 1999) showed that every instance of the first parameterized problem can be transformed, in polynomial time, into an equivalent one with at most 6k+3 variables and 10k clauses.We improve this to 4k variables and (2√5+4)k clauses. Mahajan and Raman conjectured that the second parameterized problem is fixed-parameter tractable (FPT). We show that the problem is indeed FPT by describing a polynomial-time algorithm that transforms any problem instance into an equivalent one with at most (7+3√5)k variables. Our results are obtained using our improvement of the Lieberherr-Specker bound above.  
References:
Robert Crowston, Gregory Gutin, Mark Jones and Anders Yeo, A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications, Algorithmica DOI 10.1007/s00453-011-9550-1
29.02.2012
Piotr Kołacz
On-line approximate string matching with bounded errors
We introduce a new dimension to the widely studied on-line approximate string matching problem, by introducing an error threshold parameter ϵ so that the algorithm is allowed to miss occurrences with probability ϵ. This is articularly appropriate for this problem, as approximate searching is used to model many cases where exact answers are not mandatory. We show that the relaxed version of the problem allows us breaking the average-case optimal lower bound of the classical problem, achieving average case O(nlog_σ m/m) time with any ϵ=poly(k/m), where n is the text size,m the pattern length, k the number of differences for edit distance, and σ the alphabet size. Our experimental results show the practicality of this novel and promising research direction. Finally, we extend the proposed approach to the multiple approximate string matching setting, where the approximate occurrence of r patterns are simultaneously sought. Again, we can break the average-case optimal lower bound of the classical problem, achieving average case O(n log_σ(rm)/m) time with any ϵ=poly(k/m).  
References:
Marcos Kiwi, Gonzalo Navarro and Claudio Telha, On-line approximate string matching with bounded errors, Theoretical Computer Science 412 (2011), 6359–6370
18.01.2012
Jonasz Pamuła
1-Local 7/5-Competitive Algorithm for Multicoloring Hexagonal Graphs
In the frequency allocation problem, we are given a cellular telephone network whose geographical coverage area is divided into cells, where phone calls are serviced by frequencies assigned to them, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e. minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph, where every vertex knows its position in the graph. We present a 1-local 7/5-competitive distributed algorithm for multicoloring a hexagonal graph, thereby improving the previous 1-local 17/12-competitive algorithm.  
References:
Petra Šparl, Rafał Witkowski, Janez Žerovnik, 1-Local 7/5-Competitive Algorithm for Multicoloring Hexagonal Graphs, Algorithmica, DOI 10.1007/s00453-011-9562-x
11.01.2012
Paweł Wanat
Exact Algorithms for Edge Domination
An edge dominating set in a graph G=(V,E) is a subset of the edges D⊆E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is NP-hard. We present a faster exact exponential time algorithm for this problem. Our algorithm uses O(1.3226^n) time and polynomial space. The algorithm combines an enumeration approach of minimal vertex covers in the input graph with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwisely. In each of these refinement steps, the worst cases in the measure and conquer analysis of the current algorithm are reconsidered and a new branching strategy is proposed on one of these worst cases. In this way a series of algorithms appears, each one slightly faster than the previous one, ending in the O(1.3226^n) time algorithm. For each algorithm in the series, we also give a lower bound on its running time. We also show that the related problems: minimum weight edge dominating set, minimum maximal matching and minimum weight maximal matching can be solved in O(1.3226^n) time and polynomial space using modifications of the algorithm for edge dominating set. In addition, we consider the matrix dominating set problem which we solve in O(1.3226^{n+m}) time and polynomial space for n×m matrices, and the parametrised minimum weight maximal matching problem for which we obtain an O∗(2.4179^k) time and space algorithm.  
References:
Johan M.M. van Rooij, Hans L. Bodlaender, Exact Algorithms for Edge Domination, Algorithmica, DOI 10.1007/s00453-011-9546-x
04.01.2012
Paweł Komosa
An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion
The PATHWIDTH ONE VERTEX DELETION (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most 1. The question can be considered as a natural variation of the extensively studied FEEDBACK VERTEX SET (FVS) problem, where the deletion of at most k vertices has to result in the remaining graph having treewidth at most 1 (i.e., being a forest). Recently Philip et al. (WG, Lecture Notes in Computer Science, vol. 6410, pp. 196–207, 2010) initiated the study of the parameterized complexity of POVD, showing a quartic kernel and an algorithm which runs in time 7^k·n^{O(1)}. In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65^k·n^{O(1)}, thus obtaining almost tight kernelization bounds when compared to the general result of Dell and van Melkebeek (STOC, pp. 251–260, ACM, New York, 2010). Techniques used in the kernelization are based on the quadratic kernel for FVS, due to Thomassé (ACM Trans. Algorithms 6(2), 2010).  
References:
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk and Jakub Onufry Wojtaszczyk, An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion, Algorithmica DOI 10.1007/s00453-011-9578-2
21.12.2011
14.12.2011,Dominik Dudzik
Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs
The HAMILTONIAN CYCLE problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in O*(α^n) time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses O*(1.657^n) time and polynomial space. The LONGEST CYCLE problem, in which the task is to find a cycle of maximum length, is a natural generalization of the HAMILTONIAN CYCLE problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the LONGEST CYCLE problem, and consequently the HAMILTONIAN CYCLE problem, for claw-free graphs: one algorithm that uses O*(1.6818^n) time and exponential space, and one algorithm that uses O*(1.8878^n) time and polynomial space.  
References:
H.J. Broersma, F.V. Fomin, P. van 't Hof and D. Paulusma, Exact algorithms for finding longest cycles in claw-free graphs, Algorithmica, DOI 10.1007/s00453-011-9576-4
07.12.2011
Wojciech Bukowicki
Bipartite Matching in the Semi-streaming Model
We present the first deterministic 1+ε approximation algorithm for finding a large matching in a bipartite graph in the semi-streaming model which requires only O((1/ε)^5) passes over the input stream. In this model, the input graph G=(V,E) is given as a stream of its edges in some arbitrary order, and storage of the algorithm is bounded by O(n polylog n) bits, where n=|V|. The only previously known arbitrarily good approximation for general graphs is achieved by the randomized algorithm of McGregor (Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and Randomization and Computation, Berkeley, CA, USA, pp. 170–181, 2005), which uses Ω((1/ε)^{1/ε}) passes. We show that even for bipartite graphs, McGregor's algorithm needs Ω(1/ε)^{Ω(1/ε)} passes, thus it is necessarily exponential in the approximation parameter. The design as well as the analysis of our algorithm require the introduction of some new techniques. A novelty of our algorithm is a new deterministic assignment of matching edges to augmenting paths which is responsible for the complexity reduction, and gets rid of randomization.

We repeatedly grow an initial matching using augmenting paths up to a length of 2k+1 for k=2/ε. We terminate when the number of augmenting paths found in one iteration falls below a certain threshold also depending on k, that guarantees a 1+ε approximation. The main challenge is to find those augmenting paths without requiring an excessive number of passes. In each iteration, using multiple passes, we grow a set of alternating paths in parallel, considering each edge as a possible extension as it comes along in the stream. Backtracking is used on paths that fail to grow any further. Crucial are the so-called position limits: when a matching edge is the i-th matching edge in a path and it is then removed by backtracking, it will only be inserted into a path again at a position strictly lesser than i. This rule strikes a balance between terminating quickly on the one hand and giving the procedure enough freedom on the other hand.  


References:
Sebastian Eggert, Lasse Kliemann, Peter Munstermann, Anand Srivastav, Bipartite Matching in the Semi-streaming Model, Algorithmica, DOI 10.1007/s00453-011-9556-8
30.11.2011
Michał Feret
Guard games on graphs
A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the guards and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges. The area protected by the guards is an induced subgraph of the given graph. We investigate the algorithmic aspects of the guarding problem, which is to find the minimum number of guards sufficient to patrol the area. We show that the guarding problem is PSPACE-hard and provide a set of approximation algorithms. All approximation algorithms are based on the study of a variant of the game where the intruder must reach the guarded area in a single step in order to win. This variant of the game appears to be a 2-approximation for the guarding problem, and for graphs without cycles of length 5 the minimum number of required guards in both games coincides. We give a polynomial time algorithm for solving the one-step guarding problem in graphs of bounded treewidth, and complement this result by showing that the problem is W[1]-hard parameterized by the treewidth of the input graph. We also show that the problem is fixed parameter tractable (FPT) parameterized by the treewidth and maximum degree of the input graph. Finally, we turn our attention to a large class of sparse graphs, including planar graphs and graphs of bounded genus, namely apex-minor-free graphs. We prove that the one-step guarding problem is FPT and possess a PTAS on apex-minor-free graphs.  
References:
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Guard games on graphs: Keep the intruder out! , Theoretical Computer Science 412 (2011), 6484–6497
23.11.2011
Albert Łącki
Almost Exact Matchings
In the exact matching problem we are given a graph G, some of whose edges are colored red, and a positive integer k. The goal is to determine if G has a perfect matching, exactly k edges of which are red. More generally if the matching number of G is m = m(G), the goal is to find a matching with m edges, exactly k edges of which are red, or determine that no such matching exists. This problem is one of the few remaining problems that have efficient randomized algorithms (in fact, this problem is in RNC), but for which no polynomial time deterministic algorithm is known. The first result shows that, in a sense, this problem is as close to being in P as one can get. We give a polynomial time deterministic algorithm that either correctly decides that no maximum matching has exactly k red edges, or exhibits a matching with m(G)−1 edges having exactly k red edges. Hence, the additive error is one. We also present an efficient algorithm for the exact matching problem in families of graphs for which this problem is known to be tractable.We show how to count the number of exact perfect matchings in K_{3,3}-minor free graphs (these include all planar graphs as well as many others) in O(n^{3.19}) worst case time. Our algorithm can also count the number of perfect matchings in K_{3,3}-minor free graphs in O(n^{2.19}) time.  
References:
Raphael Yuster, Almost Exact Matchings, Algorithmica, DOI 10.1007/s00453-011-9519-0
16.11.2011
09.11.2011
02.11.2011
Lech Duraj
Grzegorz Herman
Garbage collection by reference counting the strongly connected components

Traditional methods of automatic collection of unreachable objects (garbage) employ reference counting and/or graph traversal. The disadvantage of the former is its inherent inability to collect cyclic garbage structures (to deal with those, a supplemental, traversal-based method is often used). The latter suffers from having to traverse (at least periodically) all reachable objects. Heuristics based on the generational hypothesis lower this overhead, but only at the cost of failing to provide strong bounds on when garbage is going to be collected or how much total memory will be used. We propose a different approach, based on counting references between (approximations of) the strongly connected components of the object graph. Our method is real-time (has a constant time bound on any single operation), and concurrent (allows to interleave collection with program's activity). It provides an arbitrarily strong bound on memory usage. It makes use of the generational hypothesis, avoiding the traversal of objects permanently reachable by "old enough" edges. It uses constant memory per managed object plus constant global memory, and employs no data structures more complex than a stack, which gives hope that it can be performed in a lock-free manner.  

26.10.2011
19.10.2011,Michał Staromiejski
When are finite rings indecomposable?
The main goal of the talk is to present a simple characterization of local (a.k.a. indecomposable) finite algebras over (finite) fields. The characterization leads to polynomial-time algorithm for testing locality of such algebras and, in turn, to polynomial-time locality test for arbitrary finite rings. Generalization for algebras over arbitrary fields and related open questions will be discussed.  
12.10.2011
05.10.2011,Leszek Horwath
Asymptotically Optimal Randomized Rumor Spreading
New protocol solving the fundamental problem of disseminating a piece of information to all members of a group of n players.  
08.06.2011
Dominik Dudzik
SeminariumIT 08.06.2011
 
01.06.2011
Kamil Kraszewski
A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
In MaxSat, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of O*(2^(K/6.2158)) for Max-2-SAT (each clause contains at most 2 literals), where K is the number of clauses. The run time has been achieved by using heuristic priorities on the choice of the variable on which we branch. The implementation of these heuristic priorities is rather simple, though they have a significant effect on the run time. Also the analysis uses a non-standard measure time.  
References:
D. Raible, H. Fernau. A new upper bound for max-2-sat: A graph-theoretic approach. MFCS, LNCS 5162, 551–562, 2008
25.05.2011
Szymon Borak
SeminariumIT 25.05.2011
 
18.05.2011
Marek Wróbel
Design and analysis of online batching systems
 
References:
Regant Y.s. Hung, Hing-Fung Ting, Design and analysis of online batching systems, Algorithmica (2010), 57: 217--231
11.05.2011
Jonasz Pamuła
SeminariumIT 11.05.2011
 
04.05.2011
Michał KukiełaUMK
Some combinatorial approaches to homotopy
Different notions of "homotopy" equivalences of partially ordered sets may be defined in terms of various one-point reductions and expansions. These have been a recent object of study of J.A. Barmak and G.E. Minian. Their research was inspired by results from the 60's of R.E. Stong, who classified, using elementary "deformations", the homotopy types of finite topological spaces.

Finite spaces satisfying the T0 separability axiom may be easily identified with partially ordered sets, and the deformations of Stong turn out to be dismantlings by irreducible points. Some, natural from a topologist's point of view, generalizations of irreducible points give interesting definitions of "homotopy".

I will present relations between these notions and their connections to topics such as poset fixed point theory, evasiveness and homotopy theory of polyhedra.  

27.04.2011
Piotr Wójcik
An Approximation Algorithm for Binary Searching in Trees
We consider the problem of computing efficent strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n) approximation.  
References:
Eduardo Laber and Marco Molinaro, An Approximation Algorithm for Binary Searching in Trees, Algorithmica, 59(2010), 601-620
20.04.2011
Piotr Szafruga
Greedy Remote-Clique Algorithm
 
References:
B.Birnbaum and K.J.Goldman, An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs
13.04.2011
Grzegorz Guśpiel
A Constant Space, Subquadratic Algorithm for Inverse Permutation
We assume the permutation is given by an array in which the i-th element denotes the value at i. Finding its inverse can be achieved in linear time with a simple cycle-based algorithm. Limiting the numbers that can be stored in our array to the range of the permutation still allows a simple O(n^2) solution. A better O(n^{3/2}) algorithm will be presented.  
06.04.2011

Cancelled
 
30.03.2011
Marek GrabowskiUW
Computing steady state of Markov Chain by combinatorial aggregation
Probabilistic model checking is receiving quite a lot of attention around the world recently (i.e. DARPA is funding PRISMATIC project). Unlike 'normal' model checking which was research for nearly 30 years, probabilistic model checking is still a young discipline.

Most common framework for modeling probabilistic processes are Markov Chains, both discrete and continuos time and Markov Decision Processes. One of interesting questions one can ask about DTMCs and CTMCs is 'to what distribution given chain converges' (what's the steady state of it).

Theory of Markov Chains has over 100 years now and analytic solutions of all interesting questions are well known. Problem with such solutions is that they're usually untraceable for real-life models, because of their size. This is the reason why iterative methods are most commonly used. Unfortunately they also fail for some examples.

I'll show an algorithm which was proposed by Pokarowski in his PhD thesis and implemented by me just recently, which for some class of models gives huge speedup in return for some precision. I'll describe theory behind this algorithm, show how it works in general and some test results. I'll also tell what modifications are on the way and what we hope to achieve in the end.  

23.03.2011
Maciej Wawro
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
Motivated by applications in batch scheduling of jobs in manufacturing systems and distributed computing, we study two related problems. Given is a set of jobs {J1, . . . , Jn}, where Jj has the processing time pj , and an undirected intersection graph G = ({1, 2, . . . , n}, E), with an edge (i, j) whenever the pair of jobs Ji and Jj cannot be processed in the same batch. We are to schedule the jobs in batches, where each batch completes its processing when the last job in the batch completes execution. The goal is to minimize the sum of job completion times. Our two problems differ in the definition of completion time of a job within a given batch. In the first variant, a job completes its execution when its batch is completed, whereas in the second variant, a job completes execution when its own processing is completed.

For the first variant, we show that an adaptation of the greedy set cover algorithm gives a 4-approximation for perfect graphs. For the second variant, we give new or improved approximations for a number of different classes of graphs. The algorithms are of widely different genres (LP, greedy, subgraph covering), yet they curiously share a common feature in their use of randomized geometric partitioning.  


References:
Leah Epstein, Magnus M. Halldórsson, Asaf Levin, Hadas Shachnai, Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs , Algorithmica 55(2009) 643-665
09.03.2011
Andrzej Grzesik
Maximum number of pentagons in triangle free graphs
 
02.03.2011
Kasper Kopeć
Fast index for approximate string matching
 
26.01.2011
19.01.2011,Michał Feret
Fast 3-coloring triangle free planar graphs
 
12.01.2011
Grzegorz Gutowski
Mr Paint and Mrs Correct go fractional
 
05.01.2011
Adam Zydroń
Improved Parameterized Set Splitting Algorithms: A Probabilistic Approach
 
15.12.2010
Przemysław Derengowski
A best online algorithm for scheduling on two parallel batch machines.
 
08.12.2010
Michał Handzlik
A fully dynamic graph algorithm for recognizing proper interval graphs
 
01.12.2010
Marcin WitkowskiUAM
Load balancing games
Load balancing games are the following kind of problems. Assume we are given M machines and N jobs. Each job i is associated with a vector p=(p_1,..,p_m), where p_j is the processing time of this job on machine j. Players correspond to jobs. The strategy set of each player is the set of machines. Given a strategy for each player, the total load on each machine is the sum of processing times of the jobs that chose that machine. The aim of each player is to minimize the total load on its chosen machine. We, as an external observer, are interested in minimizing the total load on the most-loaded machine.
We call a Nash Equilibriun (NE), a strategy profile (vector consist of choices of each player) that is resilient to unilateral deviations, which means that no player has anything to gain by changing only his or her own strategy unilaterally. A downside of NE is that it is not necessarily stable against deviations by coalitions of players. A pure Nash equilibrium which is resilient to deviations by coalitions is called a strong equilibrium (SE). Using a framework introduced by Feldman and Tamir [1] I estimate how close a NE is to SE in certain load balancing games.  
References:
[1] M. Feldman and T. Tamir. ,,Approximate strong equilibrium in job scheduling games". In SAGT, pages 58-69, 2008.
24.11.2010
Jakub Kozik
Secretary problem on partial orders.
n secretaries apply for a single secretary position. All the candidates are partially ordered according to their competences. They are interviewed one by one in a random order. After each interview we know only the induced partial order on the secretaries interviewed so far. The decision whether to accept or reject a candidate must be made just after the interview. The objective is to choose one of the maximal candidates.
We are going to present some recent result in the search for optimal strategy, with special emphasis on the result by R. Freji and J. Wästlund whose strategy achieves probability of success 1/e on every partial order.  
References:
Freij, Ragnar; Wästlund, Johan; Partially ordered secretaries; Electronic Communications in Probability; Vol. 15 (2010) paper 45, pages 504-507.
10.11.2010
Bartosz Walczak
An extremal problem for crossing vectors
Two vectors u,v ∈ Zw are called crossing if there are two coordinates i,j such that uivi ≥ 1 and vjuj ≥ 1. They are called k-crossing if there are two coordinates i,j such that uivi ≥ k and vjuj ≥ k. We consider the following question: what is the maximum size of a family of pairwise crossing but not k-crossing vectors in Zw? Several (totally different) constructions of such families of size kw−1 are known. The conjecture is that kw−1 is optimal.

The problem has been posed by Felsner and Krawczyk in February 2010. Since then several groups have been trying hard to solve it, with only little success. The conjecture is trivial for w=1,2. I will present the proof for w=3. It is not clear whether it brings us closer to the proof of the general conjecture, but it seems promising. For w≥4 the question is open. Solving the problem for general w might give us some new insights into posets and Sperner theory.  

03.11.2010
27.10.2010,Grzegorz Matecki
First-Fit coloring of co-comparability graphs
One of the simplest heuristics to obtain a proper coloring of a graph is First-Fit algorithm. First-Fit visits each vertex of a graph in the already given order and assigns to it the smallest possible number (color) such that two vertices connected by an edge are not monochromatic. The class of 2-colorable co-comparability graphs is known to be infinitely colorable by First-Fit. We proved that H-free co-comparability graphs with a fixed chromatic number are finitely colorable by First-Fit if and only if H is a 2-colorable co-comparability graph. It provides the full characterization of First-Fit on co-comparability graphs in terms of forbidden structures.

This is a joint work with Bartłomiej Bosek and Tomasz Krawczyk.  

20.10.2010
13.10.2010,Marek Adrian
Contributions of Endre Szemerédi in theoretical computer science
This talk is based on one given by Avi Wigderson presented on a conference honoring of the 70th birthday of Endre Szemerédi. Out of several results we will look closely into three proofs Szemerédi participated in. At first we will check the Dictionary Problem. We want to store a set U = {u1, … , un} subset 2k (n<<2k) using O(n) time & space. The question is how to minimize the number of queries to determine if x is in U. Next we shall look at Sorting Network where one using O(nlogn) comparators has been explicitly given. Finally we shall compare deterministic and non deterministic algorithms in linear time and their impact on k-paged graphs.  
06.10.2010
Torsten UeckerdtTechnical University Berlin
Intersection graphs of gridpaths
We are considering so called EPG representations of simple graphs, that is every vertex is modeled by a path in the plane square grid, such that the paths of two vertices have a grid-edge in common iff the two vertices are adjacent. The bend-number b(G) of a graph G is the minimal number k, such that G has an EPG representation with each path having no more than k bends. The bend-number is related to a graph's interval-number and track-number. For certain graph classes (planar graphs, complete bipartite graphs, graphs with maximum degree D, ...) we are now interested in the maximum interval-, track-, and bend-number among all graphs in the class. We settle some answers but still are left with many open questions.  
09.06.2010
Tomasz Krawczyk
On-line dimension for posets excluding two long chains
 
02.06.2010
Maciej Wawro
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
 
26.05.2010
Mateusz Drewienkowski
Priority algorithms for graph optimization problems
 
19.05.2010

cancelled
 
12.05.2010
Przemysław Gordinowicz
TU Łódź
On graphs isomorphic to their neighbour and non-neighbour sets

The talk describes a construction of a universal countable graph, different from the Rado graph, such that for any of its vertices both the neighbourhood and the non-neighbourhood induce subgraphs isomorphic to the whole graph. This solves an open problem posed by A. Bonato at 18th BCC
 

05.05.2010
Szymon Borak
Optimal algorithms for the path/tree-shaped facility location problems in trees
 
28.04.2010
Kasper Kopeć
Finding paths between graph colorings: PSPACE-completeness
 
07.04.2010
31.03.2010,Kamil Kraszewski
Preemptive online scheduling: optimal algorithms for all speeds
 
24.03.2010
17.03.2010,Piotr Micek
Algorithmic version of the Lovász Local Lemma
We will study the new approach of Robin Moser to give an algorithm for the Lovász Local Lemma. Most likely, we will stick to symmetric case.  
References:
R. A. Moser, G. Tardos - A constructive proof of the general Lovász Local Lemma
20.01.2010
Grzegorz Herman
Unambiguous Functions in Logarithmic Space
 
13.01.2010
06.01.2010,Grzegorz Matecki
On-line matching on bipartite graphs
We consider bipartite matching in the on-line version as follows. There is a bipartite graph G=(U,V,E), in which vertices in V are given a priori and each vertex u in U arrives in the on-line fashion (with all its incident edges). An on-line algorithm matches each such vertex u to a previously unmatched adjacent vertex in V, if there is one. Decisions made by the algorithm are irrevocable. The objective is to maximize the size of the resulting matching. It is easy to observe that any greedy algorithm (never leave vertex u unmatched if a match is possible) matches at least n/2 edges where n is the size of the optimal matching with G given at once. This number is optimal and there is no better algorithm.

We propose the following modification of an on-line matching. The algorithm matches each incoming vertex u in U to a set S(u) of adjacent vertices in V (instead of one vertex). In case when S(u) and S(x) for already existing x in U are not disjoint the algorithm must remove all common vertices from S(x). Additionally, the algorithm has to obey the rule: each S(x) must not become empty if only it was initialized with a nonempty set of vertices. An algorithm satisfying the above condition is called adaptive. In this approach a vertex u in U can be always matched to a vertex from S(u) (if S(u) is not empty). Therefore, the number of matched edges is equal to the number of nonempty sets S(u).

We are going to present the optimal adaptive on-line algorithm which breaks n/2 barrier and matches at least 0.589n+o(n) edges.  

16.12.2009
Radosław Kożuch
An O(m^2 n) Alghorithm for Minimum Cycle Bases of Graph
Cycles in graphs play an important role in many applications, e.g., analysis of electrical networks, analysis of chemical and biological pathways, periodic scheduling, and graph drawing. Cycle bases are a compact description of the set of all cycles of a graph and cycle bases consisting of short cycles or, in weighted graphs, of small weight cycles are preferable. I will present an algorithm for computing minimum cycle basis in an undirected graph in time O(E^2*V + E*V^2*log V).  
References:
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch, An O(m^2 n) Algorithm for Minimum Cycle Basis of Graphs, Algorithmica (2008) 52: 333–349
09.12.2009
Bartłomiej Bosek, Tomasz Krawczyk
Subexponential algorithm for on-line chain partitioning problem (cont.)
 
02.12.2009
Grzegorz Matecki
Golden ratio in on-line chain partitioning problem
Consider a game with two players. The first one, called Spoiler, reveals points of an order, one at a time. The second one, called Algoritm, assigns each new point to some chain and so maintains a chain partition of an incoming order. The aim of Algoritm is to use the smallest number of chains as possible. Whereas Spoiler tries to force Algoritm to use as much as possible different chains.

The talk is on a variant of this game where Spoiler reveals a semi-order and each new point is maximal at a time it arrives.

We present a strategy for Algoritm using at most gw chains where g is a golden ratio (g=1,618..) and w is optimal (off-line) number of chains. Moreover, we prove that it is best possible. Our strategy somehow induces a system of linear inequalities incorporating w (off-line optimum) as well as the number of chains used by Algoritm. The solution of this system shows how the golden ratio is involved in decisions made by Algoritm.  
References:
Stefan Felsner, Kamil Kloch, Grzegorz Matecki and Piotr Micek, On-line chain partitioning of up-growing semi-orders, submitted
25.11.2009
Andrei KrokhinDurham University
On the hardness of losing weight
Local search algorithms iteratively improve solutions by checking whether it is possible to find a better solution in the local neighborhood of the current solution. The local neighborhood is usually defined as the set of solutions that can be obtained by one (or more generally, at most k for some fixed k) elementary changes. Large values of k can give better results; however, the brute force search of the local neighborhood is not feasible for larger k. Parameterized complexity gives a convenient framework for studying the question whether there is an efficient way of searching the local neighborhood. In the talk, I will briefly overview parameterized complexity, summarize recent results in this direction, and explain in more detail the analysis of the problem of finding minimum weight solutions for Boolean CSP.
(Joint work with Dániel Marx)  
18.11.2009
04.11.2009
28.10.2009
Bartłomiej Bosek
Tomasz Krawczyk
Subexponential algorithm for on-line chain partitioning problem

An on-line chain partitioning algorithm receives the elements of a poset, point by point, from some externally determined list. When a new point is presented the algorithm learns its comparability status with previously presented points and makes an irrevocable choice of a color, keeping the invariant that all points with the same color form a chain. The choice of a color is made without knowledge of future points. The number of colors used by an on-line algorithm is usually compared to the width w of the poset. Kierstead showed that there exists an on-line algorithm that covers any poset with (5^w-1)/4 chains. On the other hand Szemeredi proved that any on-line algorithm for the on-line chain partitioning problem has to use at least (w^2+w)/2 colors. We reduce the huge gap between the exponential upper bound and the polynomial lower bound by improving the upper bound to the subexponential function: in fact we show an on-line chain partitioning algorithm that uses at most w^O(log w) many colors.  

21.10.2009
14.10.2009,Piotr Micek,Bartosz Walczak
Graph eating games
Alice and Bob share a connected graph. Its vertices are weighted with non-negative values summing up to one. The players eat the vertices alternately one by one (starting with Alice) until no vertex is left. The rule they have to obey is that after each move the vertices eaten so far form a connected subgraph of the original graph. Both players want to maximize their final gain, i.e., the total weight of the vertices they have eaten. This game for a cycle is known as the pizza eating problem. Recently, Knauer, Micek and Ueckerdt proved that Alice can eat 4/9 of any cycle (pizza), which is best possible and settles the conjecture of Peter Winkler.

In the general game, Alice cannot guarantee herself any positive constant gain on all connected graphs. Curiously, the parity of the number of vertices makes a difference. Examples of graphs with small Alice's gain having an odd number of vertices need a very rich structure, contrary to strikingly simple examples with an even number of vertices. In particular, there are trees with an even number of vertices which are very bad for Alice, while she can guarantee herself a positive constant gain on all odd trees.

We wish to introduce the audience to this and similar games on graphs. Our techniques are quite general and seem to be applicable to other combinatorial games as well.  
07.10.2009
Tomasz Jurkiewicz
Breaking through the O(m^2 n) Barrier for Minimum Cycle Bases
Cycles in graphs play an important role in many applications, e.g., analysis of electrical networks, analysis of chemical and biological pathways, periodic scheduling, and graph drawing. Cycle bases are a compact description of the set of all cycles of a graph and cycle bases consisting of short cycles or, in weighted graphs, of small weight cycles are preferable. We will present an algorithm for computing general minimum weight cycle bases in time O(E^omega) for general graphs; here V and E denote the number of nodes and edges, respectively, and omega is the exponent of the fastest matrix multiplication algorithm. Our algorithm is the first to run faster than Otilde(E^2 V). A key to our improved running time is the insight that the search for the minimum basis can be restricted to a set of candidate cycles of total length O(V E).  
References:
Edoardo Amaldi, Claudio Iuliano, Tomasz Jurkiewicz, Kurt Mehlhorn and Romeo Rizzi. Breaking the O(m^2 n) Barrier for Minimum Cycle Basis, ESA 2009
16.09.2009
Lê Đại Trí MẫnUniversity of Toronto
An introduction to generalized combined traces
Mazurkiewicz traces were introduced by A. Mazurkiewicz in 1977 as a language representation of partial orders to model "true concurrency". The theory of Mazurkiewicz traces has been utilized to tackle not only various aspects of concurrency theory but also problems from other areas, including combinatorics, graph theory, algebra, and logic.

However, neither Mazurkiewicz traces nor partial orders can effectively model more complex relationships, e.g., "not later than". In this talk, I will introduce the theory of generalized combined traces (generalized comtraces). Generalized comtraces are generalizations of Mazurkiewicz traces, where generalized stratified order structures are used instead of partial orders. This allows us to model even the most general case of concurrent behaviors under the assumption that observations are stratified orders. The theory of generalized comtraces also provides us a wide variety of new and interesting problems to work on.  


References:
R. Janicki and D.T.M. Le, Modelling Concurrency with Comtraces and Generalized Comtraces, preprint can be found at http://arxiv.org/abs/0907.1722
10.06.2009
Michal Handzlik
Online unit clustering
Online unit clustering is a clustering problem where classification of points is done in an online fashion, but the exact location of clusters can be modified dynamically. We study several variants and generalizations of online unit clustering problem, which are inspired by variants of packing and scheduling problems in the literature  
03.06.2009
Michał WronaWrocław University
Quantified Positive Temporal Constraints
A quantified constraint satisfaction problem (qcsp) is a version of a constraint satisfaction problem (csp) where variables occurring in an input formula can be not only existentially but also universally quantified. We say that a relation is temporal positive if it has a positive first order definition over the order of rational numbers. Our main contribution is a complexity characterization of qcsp(L) for all finite sets of positive temporal relations L. The complexity of these problems varies. Some of them are in LOGSPACE, some are NLOGSPACE-complete, P-complete, NP-complete, or PSPACE-complete.  
28.05.2009
Andrzej RucińskiUAM Poznań
2nd Discrete Integration Meeting & SSAK
Campus AGH, building B7, room 1.9, Thursday, May 28, at 16:00 (sharp)  
20.05.2009
Sylwia Antoniuk
Efficient on-line repetition detection
A repetition is a nonempty string of the form X^q, where q >= 2. Given a string S character by character and the value of q, the on-line repetition detection problem is to detect and report the first repetition in S, if it exists, in an on-line manner. Leung, Peng and Ting first studied the problem for q=2 and gave an O(m log^2 m) time algorithm, where m is the ending position of the first repetition in S. We improve the above work by reducing the time complexity to O(m log B), where B is the number of distinct characters in the first m characters of S. Moreover, we also solve the problem for q >= 3 with the same time complexity.  
13.05.2009
Andrzej Kukier
Similarity Search in High Dimensions via Hashing
The nearest- or near-neighor query problems arise in a large variety of database applications, usually in the context of similarity searching. Of late, there has been increasing interest in building search/index structures for performing similarity search over high-dimensional data, e.g. image databases, document collections, time-series databases and genome databases. Unfortunately, all known techniques for solving this problem fall prey of the "curse of dimensionality". That is, the data structures scale poorly with data dimensionality: in fact, if the number of dimensions exceeds 10 to 20, searching in k-d trees and related data structures involves the inspection of a large fraction of the database, therby doing no better than brute-force linear search. It has been suggested that since the selection of features and the choice of a distance metric in typical applications is rather heuristic, determinig an approximate nearest neighbor should suffice for most practical purposes. In this paper, we examine a novel scheme for approximate similarity search bases on hashing. The basic idea is to hash the points for the database so as to ensure that the probability of a collision is much higher for objects that are close to each other than for those that are far apart. We provide experimental evidence that our method gives significant improvement in running time over other methods for searching in high-dimensional spaces based on hierachical tree decomposition. Experimental results also indicate that our scheme scales well even for a relatively large number of dimensions (more than 50).  
06.05.2009
Piotr Cieślik
Edge-Coloring Bipartite Multigraphs in O(E log D) Time
For V, E and D denoting the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G, it is shown that a minimal edge-coloring of G can be computed in O(E log D) time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time.  
29.04.2009
Bartłomiej Bosek
Posets omitting two incomparable chains of the same height
We consider a problem of partitioning a poset into chains by First-Fit algorithm. In general this algorithm uses arbitrarily many chains on a class of bounded width posets. In this paper we prove that First-Fit uses at most $4tw^2$ chains to partition any poset of width $w$ which does not induce two incomparable chains of height $t$. In this way we get a wide class of posets with polynomial bound for the on-line chain partitioning problem. We discuss also some consequences of our result for coloring graphs by First-Fit.  
References:
B. Bosek, T. Kraczyk and E. Szczypka, First-Fit algorithm for on-line chain partitioning problem, manuscript, 2009.
22.04.2009
Tomasz Schoen
Spectral gaps and sum-sets
 
01.04.2009
Kolja Knauer
Chip-Firing, Antimatroids, and Polyhedra
Starting from the chip-firing game of Björner and Lovász we consider a generalization to vector addition systems that still admit algebraic structures as sandpile group or sandpile monoid. Every such vector addition language yields an antimatroid. We show that conversely every antimatroid can be represented this way. The inclusion order on the feasible sets of an antimatroid is an upper locally distributive lattice. We characterize polyhedra, which carry an upper locally distributive structure and show that they can be modeled by chip-firing games with gains and losses. At the end we point out a connection to a membership problem discussed by Korte and Lovász.  
25.03.2009
Apoloniusz Tyszka
A hypothetical upper bound for solutions of a Diophantine equation with a finite number of solutions

Let E_n be the set of all equations of the form
x_i = 1, or
x_i + x_j = x_k, or
x_i * x_j = x_k,
where i,j,k range over {1,...,n}. Moreover let K be one of the rings Z,Q,R,C. We construct a system S of equations from E_{21} such that S has infinitely many integer solutions and S has no integer solution in the cube [-2^{2^{21-1}},2^{2^{21-1}}]^{21}. We conjecture that if a system S, contained in E_n, has a finite number of solutions in K, then each such solution (x_1,...,x_n) satisfies (|x_1|,...,|x_n|) \in [0,2^{2^{n-1}}]^n. Applying this conjecture for K=Z, we prove that if a Diophantine equation has only finitely many integer (rational) solutions, then these solutions can be algorithmically found. On the other hand, an affirmative answer to the famous open problem whether each listable subset M of Z^n has a finite-fold Diophantine representation would falsify our conjecture for K=Z.

Full text: http://arxiv.org/abs/0901.2093  
References:
A. Kozlowski and A. Tyszka, A Conjecture of Apoloniusz Tyszka on the Addition of Rational Numbers, 2008,
Yu. Matiyasevich, Hilbert's tenth problem: what was done and what is to be done. Hilbert's tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), 1-47, Contemp. Math. 270, Amer. Math. Soc., Providence, RI, 2000
A. Tyszka, A system of equations, SIAM Problems and Solutions (electronic only), Problem 07-006, 2007,
A. Tyszka, Some conjectures on addition and multiplication of complex (real) numbers, Int. Math. Forum 4 (2009), no. 9-12, 521-530,
A. Tyszka, Bounds of some real (complex) solution of a finite system of polynomial equations with rational coefficients

18.03.2009
04.03.2009
Grzegorz Gutowski
Multicommodity Max-Flow Min-Cut Theorems

The results of two papers will be presented:

T. Leighton, S. Rao "Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms"

Abstract: In this paper, we establish max-flow min-cut theorems for several important classes of multicommodity flow problems. In particular, we show that for any n-node multicommodity flow problem with uniform demands, the max-flow for the problem is within an O(log n) factor of the upper bound implied by the min-cut. The result (which is existentially optimal) establishes an important analogue of the famous 1-commodity max-flow min-cut theorem for problems with multiple commodities.

 

O. Günlük "A New Min-Cut Max-Flow Ratio for Multicommodity Flows"

Abstract: We present an improved bound on the min-cut max-flow ratio for multicommodity flow problems with specified demands. To obtain the numerator of this ratio, capacity of a cut is scaled by the demand that has to cross the cut. In the denominator, the maximum concurrent flow value is used. Out new bound is proportional to log(k*) where k* is the cardinality of the minimal vertex cover of the demand graph.  

28.01.2009
Rafał Józefowicz
On-line interval coloring with packing constraints
 
21.01.2009
Lech Duraj
Optimal orientation problem for different graph classes
We consider the problem of giving direction to every edge of an undirected graph, such that the number of connected pairs of vertices is maximal. In an on-line variant, the vertices of graph are given one-by-one, and the algorithm's decisions are permanent. Despite the fact that off-line algorithm always gives an orientation with O(n^2) connected pairs, the optimal outcome of the on-line algorithm can vary from O(n) to O(n^2), depending of the additional rules imposed on the graph. I'll present several possible sets of rules with different strategies and outcomes.  
14.01.2009
Michał MorayneTU Wrocław
How to choose the best twins
We consider a variant of the secretary problem where each candidate has an identical twin that applies for the same job. We find both an optimal strategy how to choose one of the best twins and the probability of success as well as the assymptotics for this probability. (with the number of candidates tending to infinity).  
07.01.2009
Bartosz Walczak
Fast route planning in road networks
I will discuss the problem of finding an optimal route between two specified nodes in a transportation network (represented as a weighted graph). When the graph is very big (as real road networks are) and there are lots of queries, one cannot afford to run a simple Dijkstra search for each individual query. Some additional structure is necessary in order to be able to answer the queries efficiently. A natural idea is to exploit hierarchical structure of road networks: only "important" roads are worth considering far away from the source and destination. Several commercial route planning systems use the formal hierarchy (freeways, national highways etc.) for this purpose. However, formal hierarchies are not perfect, and the route found this way not be optimal. The modern approach is to compute an appropriate hierarchy from scratch in the preprocessing step, based on the bare graph. After that, each query can be quickly answered with an exact optimal solution. I will present several ways of achieving this goal.  
References:
P. Sanders, D. Schultes, Engineering Fast Route Planning Algorithms, 2007.
P. Sanders, D. Schultes, Engineering Highway Hierarchies, 2006.
17.12.2008
Sebastian Czerwiński University of Zielona Góra
Short proof of Combinatorial Nullstellensatz
 
03.12.2008
Libor Barto Charles University, Prague
Constraint Satisfaction Problems of Bounded Width
We prove an algebraic characterization of applicability of the bounded width algorithm solving problem posted by Larose and Zadori.  
26.11.2008
Jan Jeżabek
Resource Augmentation for Packet Switching with Agreeable Deadlines
We study a scheduling problem known as on-line packet switching. We utilize a technique called resource augmentation, where an optimal off-line algorithm is compared against an on-line algorithm with more processing power, i.e. one that can transmit more than one packet per unit of time. A previous result showed that regardless of the processing power of the on-line algorithm there are instances on which it is outperformed by the off-line algorithm. We will show that if the jobs in the instance have aggreeable deadlines (i.e. for any jobs i,j the time interval where i is available is not contained in the interior of the time interval where j is available) a resource augmented on-line algorithm which executes two jobs per time slot will always perform at least as well as the optimal off-line algorithm.  
19.11.2008
12.11.2008,Michał Staromiejski
Computing isomorphisms between certain finite rings
For a given finite field $F$ and two polynomials $f, g \in F[X]$, there is a polynomial-time algorithm deciding whether the (finite) rings $F[X]/(f)$ and $F[X]/(g)$ are isomorphic? However, a question about constructing an isomorphism provided the rings are isomorphic seems to be more challenging. In 1991, Lenstra showed that such an isomorphism can be computed in deterministic polynomial time if the polynomials $f$ and $g$ are irreducible over $F$. There is an obvious algorithm that can solve the general problem if we allow randomization. In the talk I will present partial results which may help to find a deterministic polynomial-time algorithm.  
05.11.2008
29.10.2008,Piotr Micek
How to eat 4/9 of a pizza
Given two players alternately picking pieces of a pizza sliced by radial cuts, in such a way that after the first piece is taken every subsequent chosen piece is adjacent to some previously-taken, we provide a strategy for the starting player to get $\frac{4}{9}$ of the pizza. This is best possible and settles a conjecture of Peter Winkler.  
References:
Kolja Knauer, Piotr Micek and Torsten Ueckerdt, How to eat 4/9 of a pizza, manuscript
15.10.2008
08.10.2008,Piotr Micek, Bartosz Walczak
Summer conferences 2008
Selected results and open problems from summer conferences are presented  
11.06.2008
Zbigniew LoncPolitechnika Warszawska
Small transversals in hypergraphs
Zbiór wierzchołków hipergrafu, który przecina wszystkie jego krawędzie nazywamy transwersalem. Klasyczny algorytm zachłanny znajdujący "mały" transwersal w hipergrafie wybiera w każdym kroku do transwersala wierzchołek należący do największej liczby krawędzi nie zawierających wierzchołków już wybranych. Analiza tego algorytmu (autorstwa Chvátala i McDiarmida) prowadzi do pewnych górnych ograniczeń na najmniejszą liczność transwersala w jednorodnym hipergrafie o zadanej liczbie wierzchołków i krawędzi. Referat będzie poświęcony pewnej modyfikacji tego algorytmu zachłannego. Jego analiza prowadzi do poprawienia ograniczeń Chvátala i McDiarmida. Rezultaty te wiążą się ze znanym kombinatorycznym problemem wyznaczenia tzw. liczb Turána. W szczególności implikują nowe dolne ograniczenia na liczby Turána w pewnych szczególnych przypadkach.  
04.06.2008
Oleg PikhurkoCarnegie Mellon University
The Stability Method for the Hypergraph Turán Problem
For a k-graph F, the Turan function ex(n,F) is the maximum size of a k-graph on n vertices not containing a copy of F. Although this function was introduced by Turan yet in 1941, very few non-trivial cases have been solved and there is an abundace of open problems. We survey some recent results, concentrating on the so-called stability approach that was used to obtain some of them.  
28.05.2008
Leszek Horwath
Simple wildcard matching
Brief review over wildcar matching algorithms. Introducting the new deterministic method of O(nlgm) complexity using Fast Fourier Transformation.  
21.05.2008
Jarosław Duda
Combinatorial invariants for graph isomorphism problem
Some topological invariants for finite graphs that can be calculated in a polynomial time are presented. They may be useful in recovering the graph up to isomorphism. At least we will see how much information they do code.  
14.05.2008
07.05.2008
Przemysław Broniek
Computational complexity of solving equation systems

We consider the computational complexity of determining whether a system of equations over fixed algebra A has a solution. This leads to two problems, SysTermSat(A) and SysPolSat(A), in which equations are built out of terms or polynomials, respectively. We are interested in characterizing those algebras, for which SysPolSat can be solved in a polynomial time. The problem has been widely studied and is open in general. We prove that the Constraint Satisfaction Problem for relational structures is polynomially equivalent to SysTermSat over unary algebras. This gives that Dichotomy Conjecture for CSP is equivalent to Dichotomy Conjecture for SysTermSat over unary algebras. We also give other partial characterizations of computational complexity of SysTermSat(A), e.g. for algebras with generic operations taking only few values. This covers wide class of four-element unary algebras.  

30.04.2008
Jan Hązła
Simplified O(n) planarity algorithm
I will present O(n)-time methods for planar embedding and Kuratowski subgraph isolation that were inspired by the Booth-Lueker PQ-tree implementation of the Lempel-Even-Cederbaum vertex addition method. Instead of performing comprehensive tests of planarity conditions embedding the edges from a vertex to its descendants, we take the edge to be the fundamental unit of addition to the partial embedding while preserving planarity. This eliminates the batch planarity condition testing in favor of a few localized decisions of a path traversal process, and it exploits the fact that subgraphs can become biconnected by adding a single edge. The method is presented using only graph constructs, but the definition of external activity, path traversal process and theoretical analysis of correctness can be applied to optimize the Shih-Hsu PC-tree as well.  
References:
John M. Boyer, Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition , Journal of Graph Algorithms and Applications 8 (3), 241-273 (2004)
23.04.2008
Sebastian CzerwińskiUniversity of Zielona Gora
On a conjecture of Brown, Graham, and Landman
 
16.04.2008
Maria Chmaj
A linear-time algorithm for finding dominators in a flowgraph
The problem of finding dominators in a flowgraph arises in many kinds of global code optimization and other settings. In 1979 Lengauer and Tarjan gave an almost-linear-time algorithm to find dominators. Several attempts at a linear-time algorithm were unsuccessful. I will talk about a linear-time algorithm which Georgiadis and Tarjan gave in 2004.  
References:
L.Georgiadis, R.Tarjan, Finding dominators revisted, In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), 862-87
09.04.2008
Tomasz Krawczyk
Dimension on-line of interval orders
 
02.04.2008
Jarek Grytczuk
Open problems
 
26.03.2008
Karol Kosinski
Faster algorithms for finding lowest common ancestors in directed acyclic graphs
We are given two new methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. The first method is surprisingly natural and solves the all-pairs LCA problem for the input dag in time O(n*m). The second method relies on a novel reduction of the all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. The running time of the algorithm is O(n^2,575), so it improves the previously known O(n^2,688) time-bound for the general all-pairs LCA problem in dags by Bender, Pemmasani, Skiena and Sumazin.  
19.03.2008
Jaroslav NesetrilCharles University, Prague
Dualities for structures
Homomorphisms dualities are related to logic, model theory, partially ordered sets and of course to coloring of graphs. In this lecture we survey the recent development related to this notion.  
12.03.2008
Tomasz BartnickiUniversity of Zielona Gora
Graph coloring with an uncooperative partner
Jacek and Placek color the vertices of a graph G alternately using given set of colors C, and with Jacek going first. Placek agrees to cooperate with Jacek by respecting the rule of a proper coloring. However, for some reason he does not want the job to be completed - his secret aim is to achieve a bad partial coloring. Is it possible for Jacek to complete the coloring somehow, in spite of Placek's insidious plan? If not, then how many additional colors are needed to guarantee that the graph can be successfully colored, no matter how clever Placek is?

 

05.03.2008
Maciej Chociej
Visibility graphs, binary space partitioning and hidden surface removal (in theory and applications)
 
27.02.2008
Jan Jeżabek
Online Buffer Management - Increasing Machine Speed
We consider the following problem: a network switch receives packets characterized by a deadline and a weight. In each step the switch can transmit a fixed number of packets (this number is called the speed of the machine). The goal of the machine is to maximize the sum of weights of the transmitted jobs. It is easily seen that any on-line algorithm is outperformed by an optimal off-line algorithm with the same speed on some instance. We will show that this is true even if the speed of the on-line algorithm is increased by an arbitrary factor with respect to the speed of the off-line algorithm.  
23.01.2008
Piotr Zieliński
Computing a longest common increasing subsequence
Computing a longest common increasing subsequence of two given sequence is classical problem in computer science. It can be solved in O(n*n*m) time and O(n*m) space using a simple dynamic programming technique. In 2004 I-Husan Yang proposed an O(n*m)-time algorithm based on the relationship between computing a longest common increasing subsequence and computing a longest common subsequence. Two years later, Yoshifumi Sakai improved the space complexity of Yang's algorithm and presented O(n+m)-space algorithm. I will talk about both algorithms, especially how to implement them efficiently.  
References:
I-Hsuan Yang, A fast algorithm for computing a longest common increasing subsequence" , 2004
Yoshifumi Sakai, A linear space algorithm for computing a longest common increasing subsequence, 2006
16.01.2008
Jiří TůmaCharles University, Prague
Recovering ENIGMA, the cipher system
 
09.01.2008
Marek ChrobakUniversity of California at Riverside
Doubling technique in approximation algorithms
This talk is based on an expository article by Claire Kenyon-Mathieu and myself, in which we show that there is a number of approximation algorithms in the literature that use essentially the same (but yet not explicitely identified) technique that we refer to as "doubling". The essence of this approach is to use exponentially increasing estimates on the optimal solution to design approximate solutions. It can be used both in offline and online approximation algorithms. Applications include several clustering, searching, facility location, and scheduling problems.  
19.12.2007
Alan Meller
TBA
 
12.12.2007
Arek Pawlik
Optimal edge ranking of trees
 
05.12.2007
Libor BartoEduard Čech Center, Prague
The algebraic approach to Constraint Satisfaction Problem, recent progress
Many decision problems in combinatorics, computer science, artificial intelligence, logic, etc. can be expressed as so called Constraint Satisfaction Problems (CSPs). For a fixed relational structure R, CSP(R) is the following decision problem:

INPUT: A relational structure $S$ of the same signature as R

OUTPUT: Is there a homomorphism ftom S into R

The central problem in this area is the Dichotomy Conjecture of Feder and Vardi stating that, for any relational structure R, CSP(R) is either solvable in polynomial time or NP-complete. I will talk about the universal algebraic approach to this problem and mention some recent developments.

 

28.11.2007
21.11.2007
14.11.2007
Andrzej Pezarski
On-line clique covering of proper interval graphs
14.11.2007
07.11.2007,Lech Duraj, Grzegorz Gutowski
Optimal orientation on-line
 
24.10.2007
17.10.2007
10.10.2007
Bartosz Walczak
Algorithmic meta-theorems and treewidth

Algorithmic meta-theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. We focuse on the model checking problem, which is to decide whether a given graph satisfies a given formula. Some restrictions of this problem to specific classes of graphs (with bounded treewidth, excluded minors etc.) turn out to be fixed-parameter tractable (fpt). We define combinatorial notions of tree decomposition, treewidth and local treewidth, and prove that MSO model checking on graphs with bounded treewidth and FO model checking on graphs with bounded local treewidth are fpt. The latter result uses Gaifman's Locality Theorem, which in one of basic tools in finite model theory. The talks are based on a paper by Martin Grohe [4].  
References:
[1] B. Courcelle. Graph rewriting: An algebraic and logic approach. Handbook of Theoretical Computer Science, volume B, pp. 194-242, 1990.
[2] J. Flum, M. Grohe. Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing, 31(1):113-145, 2001.
[3] H. Gaifman. On local and non-local properties. Proceedings of the Herband Symposium, Logic Colloquium `81, pp. 105-135, 1982.
[4] M. Grohe. Logic, graphs, and algorithms. 2007.
http://www2.informatik.hu-berlin.de/~grohe/pub/meta-survey.pdf

03.10.2007
Jan Jeżabek
ICALP, LICS, LCC 2007
Selected results and open problems from ICALP, LICS, LCC 2007 are presented  
13.06.2007
Mateusz Kostanek
On k-server problem
The on-line k-server problem is set on a metric space inhabited by k servers. Initially, each sever is positioned at some point of the space. Over time, request arrive for service at points of the space. Immediately after a request at some point q comes in, a server must be moved to q in order to serve the request. When a server moves it incurs a cost equal to the distance it covers. Our goal is to design on-line algorithm which will decide which server to move when a request arrives so that any sequence of request can be served with cost as small as possible. In this talk we will present the work function algorithm for the k-server problem and prove that it has competitive ratio at most 2k-1  
References:
M. S. Manase, L. A. McGeoch, And D. D. Sleator: Competitive algorithms for on-line problems
E. Koutsoupias, C. Papadimitriou: On th k-Server conjecture
06.06.2007
Josh Buresh-OppenheimSimon Fraser University
Formalizing Algorithmic Paradigms
Since most algorithms that people use can intuitively be classified into large paradigms of algorithms such as greedy, dynamic programming, linear and semidefinite programming, local search, etc., it is natural to ask what problems can be computed by these paradigms. This question can be seen as an alternative to asking what problems can be computed by all, say, poly-time algorithms in that the restriction on the algorithms is more conceptual rather than complexity-theoretic. As we will illustrate, it is also a question of vital importance to algorithm designers. Of course, to ask a question about an algorithmic paradigm, you first have to formally define the paradigm. We offer one very natural model, pBT, which captures many algorithms generally considered to be dynamic programming or backtracking. We demonstrate upper and lower bounds in this model for problems such as interval scheduling and SAT. We also present a very powerful model for linear and semidefinite programming due to Lovasz and Schrijver and show some strong lower bounds for SAT.  
30.05.2007
Mateusz Kostanek
On k-server problem
 
23.05.2007
Michał Staromiejski
Elliptic curves
 
16.05.2007
Edyta SzymańskaUAM
The complexity of perfect matchings in hypergraphs
Given a k-uniform hypergraph H=(V,E) on n vertices, we define a perfect matching as a set of $\lfloor n/k\rfloor$ disjoint edges in E(H). From the algorithmic perspective, a few natural problems regarding this notion can be considered. One is a decision problem asking whether a given k-uniform hypergraph contains a perfect matching, which is NP-complete for k>2. In view of this fact, a question arises, under which additional conditions for a k-uniform hypergraph there exists a polynomial time algorithm finding a perfect matching in it. We define the minimum collective degree $\delta_{k-1}(H)$ to be the largest integer d such that every (k-1)-element set of vertices of H belongs to at least d edges of H. In this talk we will present an algorithm which finds a perfect matching in a k-uniform hypergraph of the minimum collective degree roughly n/2 in polynomial time. On the negative side, we will prove that the problem of deciding whether a given k-uniform hypergraph H with $\delta_{k-1}(H)> c|V(H)|$ for c<1/k contains a perfect matching is NP-complete.  
09.05.2007
Michał Staromiejski
Elliptic curves
 
25.04.2007
18.04.2007
11.04.2007
Mateusz Juda
Hypergraphs isomorphism problem

Graph isomorphism (GI) is one of the few remaining problems in NP whose complexity status couldn't be solved by classifying it as being either NP-complete or solvable in P. Nevertheless, efficient (polynomial-time or even NC) algorithms for restricted versions of GI have been found over the last four decades. Depending on the graph class, the design and analysis of algorithms for GI use tools from various fields, such as combinatorics, algebra and logic. In this talk, we collect several complexity results on graph isomorphism testing and related algorithmic problems for restricted graph classes from the literature. Further, we provide some new complexity bounds (as well as easier proofs of some known results) and highlight some open questions  
References:
J.Kobler, On Graph Isomorphism for Restricted Graph Classes

04.04.2007
Jan Jeżabek
SeminariumIT 04.04.2007
 
28.03.2007
21.03.2007
14.03.2007
07.03.2007
Kamil Kloch
Piotr Micek
Grzegorz Matecki
On-line chain partitioning of semi-orders
28.02.2007
Maciej Gazda
Polar SAT and related graphs
 
References:
Igor Zverovich, Olga Zverovich: "Polar SAT and related graphs"
24.01.2007
Piotr Danilewski
Hardness results for cake cutting
 
17.01.2007
Tomasz Jurkiewicz
Towards a trichotomy for quantified H-coloring
A very natural generalisation of graph coloring problems is defined in terms of graph homomorphism; the problem takes as input a graph G and accepts it if, and only if, there exists a homomorphism into a fixed graph H. This problem is known as the H-coloring problem and is tractable if H is bipartite and NP-complete otherwise. Quantified H-coloring problem is definable via two-player games and is tractable if H is bipartite; NP-complete if H is not bipartite and not connected; and, PSPACE-complete if H is connected and contains a unique cycle which is of odd length. (Conjecture: Problem is PSPACE-complete if H is not bipartite and connected.)  
References:
B.Martin and F.Madeleine, Towards a trichotomy for quantified H-coloring
10.01.2007
Arek Pawlik
Page rank
 
03.01.2007
13.12.2006,Wiktor Żelazny
Recognizning Interval Bigraphs
We introduce the class of interval bigraphs, bipartite graphs similiar to interval graphs. We present algorithm that recognizes these graphs in polynomial time, shown by Muller in 1993. Also a characterization of interval bigraphs in terms of their complement graphs due to Hell and Huang (2003) will be presented.
 
06.12.2006

Solutions to MWPZ 2006 problems
 
29.11.2006
22.11.2006,Jacek Krzaczkowski
Complexity of term equation problem, cntd.
 
15.11.2006
Tomasz Gorazd
Complexity of term equation problem, cntd.
 
08.11.2006
Stefan Felsner TU Berlin
Embeddings of Planar Graphs
A graph is planar if it admits a crossing-free drawing in the plane. In the first instance, such a drawing can be everything but nice. I sketch approaches to obtain nice drawings. A particularly elegant method goes back to work of W. Schnyder. He succeded in producing straight-line embeddings of planar graphs on small grids. I show how Schnyder's ideas continue to produce new insights and results. In particular it turns out that good drawings in the plane can be obtained via a detour through dimension three.  
25.10.2006
Tomasz Gorazd
Complexity of term equation problem
We study the computational complexity of the problem of satisfiability of equation between terms over a finite algebra (TERM-SAT). We describe many classes of algebras where the complexity of TERM-SAT is determined by the clone of term operations. We classify the complexity for algebras generating the maximal clones. Using this classification we describe a lot of algebras where TERM-SAT is NP-complete. We classify the situation for clones generated by an order or a permutation relation. We introduce the concept of semiaffine algebras and show polynomial time algorithms solving the satisfiability problem for them.  
20.10.2006
Hal KiersteadArizona State University
18:15 On-line Ramsey Theory
Two players, Builder and Painter, play the following game on a fixed set of vertices V. In one round Builder presents an edge e linking two previously independent vertices of V and Painter paints e using one of c colors. Builder's goal is to force Painter to create a monochromatic copy of a fixed graph F. If there are no other restrictions then Painter has no chances to avoid F (by Ramsey's theorem). But what if Builder is not allowed to construct a graph whose chromatic number exceeds that of F? We prove that even with this obstacle Builder wins this game for any number of colors. Our main tool is an auxiliary "Ramsey survival game", which is interesting in it's own right. (Joint work with Goran Konjevod)  
11.10.2006
Arkadiusz Pawlik
Integer programming and counting lattice points in rational convex polyhedra
It is possible to solve the linear programming problem in polynomial time, but if we require that the solution is integral, then the problem becomes NP-hard. However, as shown by Lenstra in 1983, if we fix the number of variables, then the problem is in P. I present a more recent approach which involves counting the solutions with generating functions.  
References:
Alexander Barvinok, James E. Pommersheim, An Algorithmic Theory of Lattice Points in Polyhedra
04.10.2006
Pawel Idziak
Open problems
 
28.06.2006
21.06.2006
14.06.2006
Grzegorz Matecki
On-line graph coloring on a bounded board

We consider a version of on-line graph coloring problem as a two person game with some additional conditions for players. Players are called Spoiler and Painter. Spoiler reveals a graph by putting or removing a node. But at each time the total number of nodes is bounded. Painter must assign a color to any new node such as two nodes connected by an edge have different colors. He cannot change colors of already colored nodes.
Chromatic number of such game for the class of graphs $C$, denoted by $\chi_C(p)$, is the smallest number of colors which is enough for Painter to color any graph presented by Spoiler, where $p$ is a bound for the size of graphs. We will show some lower and upper bounds of $\chi$-number for various classes of graphs.  

07.06.2006
31.05.2006,Bartosz Walczak
Flows in skew-symmetric networks
The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. The idea behind the solution is to find a good initial flow and then to augment the flow along so-called regular paths. The initial flow can be a slightly modified antisymmetrization of an ordinary maximum flow. Finding regular augmenting paths is based on Edmonds' "blossom" algorithm for finding a maximum matching. The resulting algorithm for MSFP is competitive with the fastest known algorithms for the maximum flow and maximum matching problems.  
References:
A. V. Goldberg, A. V. Karzanov. "Maximum skew-symmetric flows and matchings". Mathematical Programming 100, 537-568 (2004)
http://www.avglab.com/andrew/pub/skew-max.pdf
A. V. Goldberg, A. V. Karzanov. "Path problems in skew-symmetric graphs". Combinatorica 16, 127-174 (1996)
http://ftp.cs.stanford.edu/cs/theory/goldberg/skew-sp.ps.Z (preliminary version)
24.05.2006
Jarosław Grytczuk,Zielona Góra
Graph coloring games for daltonists
Ann and Ben are coloring alternately the vertices of a graph G using a fixed set of colors, with Ann playing first. They both have to respect the rule of a proper coloring, that is, none of them is allowed to create a monochromatic edge at any moment of the game. Ann's goal is to color the whole graph successfully, in which case she is a winner. Ben's goal is of course different: he perfidiously tends to create a partial coloring that cannot be extended to the whole graph, without introducing new colors. In this case he is a winner.

The game chromatic number of a graph G, denoted g(G), is the least number of colors guaranteeing a win for Ann. The main open problem is to find out how large is g(G) for planar graphs. Curiously, currently best strategy allows Ann to win (with 17 colors) even as a completely color blind person! I will present this and other techniques in a most recent treatise.

Joint work with Tomasz Bartnicki, Hal Kierstead and Xuding Zhu  

17.05.2006
Lech Duraj
TBA
 
10.05.2006
Tadeusz Prochwicz
Algorithms for four variants of the exact satisfiability problem
 
References:
V.Dahllof, P.Jonsson and R.Biegel, Algorithms for four variants of the exact satisfiability problem, Theoretical Computer Science, 320(2004), 373-394.
26.04.2006
Gabor Kun,Loránd Eötvös University, Budapest
Forbidden patterns and homomorphism problems
We say that two subclasses of NP are (computationally) equivalent if for every language in one class there is a polynomially equivalent one in the other class. A typical equivalence class is the class of k-colouring problems (k in N), it is always in P or NP-complete. NP turned out not to be equivalent to this class (unless P=NP): there is a problem in NP which is neither in P nor NP-complete.

We show some types of combinatorial problems like edge colourings or graph decompositions expressing the full computational power of the NP class. Hence these problem classes contain also some problems of "exotic" complexity.

The first natural candidate that seems not to be equivalent to NP is the class called MMSNP (Monotone Monadic Strict NP) or Forbidden patterns problem. (A typical example for a language in the class: graphs with vertex set partitionable into two subsets without triangle.) This class is conjectured to contain only NP-complete and polynomial time solvable problems.

We prove that the class MMSNP can be expressed in the simpler terminology of relational structure homomorphism problems (called Constraint Satisfaction Problems): such a language contains for a fixed structure A the relational structures that can be mapped to A. homomorphically. The first such result was only a random equivalence. The proof of the deterministic equivalence uses some type of expander structures, a typical tool in derandomization.  

19.04.2006
Jarosław Duda
Optimal coding by random algorithms
Each point of the plane grid Z^2 is labelled by 1 bit : "0" or "1". Forbiding two 1's to be adjacent reduces average information capacity (i.e., entropy) to 0.588 bit/point.
The talk gives an intuitive background to symmetry, theory of information and statistical approach to combinatorial problems. We address and discuss the following problems:
- how typical labeling looks like?
- how to generate these labelings?
- how to use these labelings to encode information?
- how to use this stuff in practice?  
29.03.2006
22.03.2006,Andrzej Soroczyński
Ulam games
Our investigation deal with searching lair game. Game was proposed by Ulam, and that is why we call it Ulam searching game with fixed number of lies. In this game one person (we call her Carole) thinks about one number from 1 to n. Second player (we call him Paul) is asking about some subset of {1,2,...,n}, and Carole reply if number she is thinking about is a member of Paul's subset. Carol is allowed to lie l(fixed number) times. Let L(l,M) be the minimum number of questions which Paul must ask to win. The main results of presented papers are:
1. For each l there exist such M that for all N >= M the following is true: L(l,2N) <= L(l,N) + 2.
2. For each l there exist such M that for all N >= M the following is true: L(l,3/2*N) <= L(l,N) + 1.  
References:
C. Deppe, Strategies for the Renyi-Ulam Game with fixed number of lies, Theoret. Comput. Sci. 314 (2004), 45-55
J. Spencer, Ulam's searching game with fixed number of lies, Theoret. Comput. Sci. 95 (1992), 307-321
22.02.2006
Andrzej Pezarski
On line clique covering of proper interval graphs presented in a connected way
Proper interval graphs are graphs for which there is a representation by intervals of real line in which no interval is contained in another. After an easy observation that all greedy algorithms have competive ratio bigger than 2 we consider all possible algorithms. Now the situation is harder: a proof that 8/5 is a lower bound in this situation will be presented.  
25.01.2006
18.01.2006
11.01.2006
Marcin Kozik
2EXPTIME-complete membership problems in algebra

We construct a finite algebra generating a variety with PSPACE-complete membership problem first. Then we show another algebra with exponentially growing gamma function. In the final construction we use both of the previously mentioned algebras to produce a finite algebra that is able to model a computation of a Turing machine on an exponentially long tape. This gives an example of a finite algebra with EXPSAPCE-hard membership problem (on the other hand this problem is known to be in a 2-EXPTIME class).  

04.01.2006
Wojciech Jawor,University of California, Riverside
Job Scheduling in Next Generation Computer Networks
Two online job scheduling problems arising in next generation computer networks are discussed.

In the first problem [3] the goal is to schedule n jobs on m identical machines, without preemption, so that the jobs complete in the order of release times and the maximum flow time is minimized. This problem arises in network systems with aggregated links, when it is required that packets complete their arrivals at the destination in the order of their arrivals at the receiver. This requirement is imposed by the IEEE 802.3 standard describing link aggregation in Local Area Networks. We present a deterministic algorithm Block with competitive ratio O(\sqrt{n/m}) and show a matching lower bound even for randomized algorithms.

The second problem [1,2] is an online unit-job scheduling problem arising in networks supporting Quality of Service. Jobs are specified by release times, deadlines and nonnegative weights. The goal is to maximize the total weight of jobs, that are scheduled by their deadlines. We show that there does not exist a deterministic algorithm with competitive ratio better than 1.618 (the golden ratio). We also give a randomized algorithm with competitive ratio 1.582, showing that randomized algorithms are provably better than deterministic algorithms for this problem.  


References:
F.Y.L.Chin, M.Chrobak, S.P.Y.Fung, W.Jawor, J.Sgall and T.Tichy, Online Competitive Algorithms for Maximizing Weighted Throughput of Unit-Jobs
W.Jawor, M.Chrobak and Ch.Dürr, Competitive Analysis of Scheduling Algorithms for Aggregated Links
14.12.2005
Maciej Żenczykowski
Online interval coloring and variants
 
References:
L. Epstein, M. Levy Online interval coloring and variants, Proc. of the 32nd ICALP (2005), 602-613
07.12.2005

Problems from Programming Competitions in Poznan 2005
 
References:
Contest home page: http://www.mwpz.poznan.pl/resources.php
30.11.2005
Piotrek Micek
The lower bound for on-line cliques covering for K_s-free graphs
 
23.11.2005
16.11.2005
19.10.2005
Iwona Cieslik
On-line coloring for graphs with forbidden subgraphs

It is known that the on-line coloring problem for arbitrary graphs is not competitive. However, restricting to special families of graphs, that have forbidden induced subgraphs (of some kind), the spoiler has his hands tied and the number of colors used by some on-line algorithms can be substantially reduced. We call these subgrahs: forcing structures. In my work I try to make a classification of competitive functions for various kind of families of graphs and also appoint the forcing structures for the on-line graph coloring. I was mostly looking for competitiveness for the graphs in the form of H-free: K_s-free, K_s,t-free, C_4-free, P_5-free and also for perfect and k-chordal graphs.  

12.10.2005
Kamil Kloch
EuroComb 2005 - Open Problems
A few open problems from the recent EuroComb conference (http://www.math.tu-berlin.de/EuroComb05/) is presented. These include the L(p, 1) labelling of graphs and the excluded subposets in the Boolean lattice.  
05.10.2005
Lech Duraj
Interval orders and dimension
Each interval order can be embedded into interval orders of sufficiently large dimension. More precisely, if X is an interval order, there exists a number t = t(X), such that for every interval order Y of dimension at least t, Y contains a subposet isomorphic to X. This is proven by embedding interval orders into some fixed structure, called "a thicket", and then finding thickets in all orders of sufficiently large dimension.  
22.07.2005
Ralph McKenzie,Vanderbilt University, Nashville TN, USA
Operations on finite structures
 
  • 1
  • 2