Optymalizacja Kombinatoryczna

Czwartek 16:15-17:45, sala 1094

Jest to seminarium magisterskie, którego tematyka dotyczy optymalizacji kombinatorycznej. W szczególności interesują nas następujące tematy:

  1.   Zaawansowane algorytmy znajdujące skojarzenia w grafach (także dwudzielnych) w przypadkach nieważonych i ważonych krawędzi.

  2.   Problemy konstruowania on-line skojarzeń w grafach dwudzielnych, AdWords Problem - rozwiązania optymalne, randomizowane.

  3.   Algorytmiczne aspekty pokrycia uniłańcuchami produktów częściowych porządków.

Strona seminarium z aktualna listą prac do zreferowania znajduje się tutaj.

Strona seminarium na UsosWeb znajduje się tutaj.

17.05.2018 16:15
Marcin Muszalski
07.06.2018 16:15
Krzysztof Maziarz
14.06.2018 16:15
Mateusz Twaróg, Patryk Urbański
Progress in the Arachne Project

Poprzednie referaty

26.04.2018 16:15
Sylwester Klocek
Colouring of (P3∪P2)-free graphs

In a paper authors are colouring of (P3∪P2)-free graphs, a super class of 2K2 -free graphs. During lecture I am going to present three discovered upper bounds of the chromatic number of (P3∪P2) -free graphs, and sharper bounds for (P3∪P2 , diamond)-free graphs and for (2K2, diamond)-free graphs. The first part of a talk will contain an explanation of terminology and notation along with problem statements and results. In the second part, I will focus on proving each result in a sequence of claims and proofs.

Arpitha P. Bharathi, Sheshayya A. Choudum, Colouring of (P3∪P2)-free graphs, Graphs and Combinatorics, Volume 34 (1), 2018
19.04.2018 16:15
Grzegorz Jurdziński
Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density

Circle packing problem, where one asks whether a given set of circles can be fit into a unit square, is known to be NP-hard. I will show that when combined area of circles does not exceed ≈0,539, then it is possible to pack them. The given bound is tight in the meaning that for larger combined area an instance impossible to pack can be found. Proof for this theorem is constructive and gives an algorithm, called Split Packing, for finding a solution for instances satisfying the conditions. Moreover it can also serve as a constant-factor approximation algorithm for the problem of finding a smallest square which can fit given circles.

Sebastian Morr, Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 99-109

12.04.2018 16:15
Maciej Woźniak
Find Your Place: Simple Distributed Algorithms for Community Detection

Graph G = (V_1 \cup V_2, E) is regular clustered graph (with two communities) if:

  • G is connected and not bipartite,
  • |V_1| = |V_2|
  • V_1 \cap V_2 = \emptyset
  • Every vertex has degree d
  • Every vertex in V_1 has exactly b neighbours in V_2 and d-b neighbours in V_1,
  • Every vertex in V_2 has exactly b neighbours in V_1 and d-b neighbours in V_2.

We define (weak) block reconstruction of graph as two-coloring of vertices that separates V_1 and V_2 up to small "error" fraction of vertices. The reconstruction is said to be strong if separation is exact.
I will present simple distributed algorithm (protocol) that produces strong reconstruction for clustered regular graphs within O(log n) iterations. I will also show that this algorithm produces weak reconstruction for non-regular clustered graphs with two communities and discuss an approach to solving this problem for regular graphs with more than two communities.

Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Trevisan, L. (2017). Find Your Place: Simple Distributed Algorithms for Community Detection. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 940-959). Philadelphia

05.04.2018 16:15
Anna Kobak
On tree-partition-width

A tree-partition of a graph G is a proper partition of its vertex set into "bags", such that identifying the vertices in each bag produces a forest. The width of a tree-partition is the maximum number of vertices in a bag. The tree-partition-width of G is the minimum width of a tree-partition of G. I will prove three theorems presented in the article, showing an upper bound on the tree-partition-width of all graphs, a lower bound for chordal graphs and a lower bound for graphs with tree-width 2.

David R.Wood, On tree-partition-width, European Journal of Combinatorics, Volume 30, Issue 5, July 2009, Pages 1245-1253

22.03.2018 16:15
Aleksandra Mędrek
The Matching Problem in General Graphs is in Quasi-NC

Authors show that the perfect matching problem in general graphs is in quasi-NC by presenting a deterministic parallel algorithm which runs in O(log^3 n) time on n^O(log^2 n) processors. The paper extends the framework of Fenner, Gurjar and Thierauf, who proved that finding perfect matching in bipartite graphs is in quasi-NC. I describe their algorithm in the first part of my presentation. In the second part I talk about difficulties that arise in the general case and how they are approached.

Ola Svensson, Jakub Tarnawski, The Matching Problem in General Graphs is in Quasi-NC, FOCS 2017

15.03.2018 16:15
Dawid Pyczek
Punctured combinatorial Nullstellensätze

This article presents an extension of Alon’s Nullstellensatz to functions of multiple zeros at the common zeros of some polynomials. It also includes an introduction to the polynomials of multiple variables and other useful definitions. There are also many corollaries useful for polynomial problem-solving. Possibly the presentation will include some geometrical usage of Nullstellensatze extensions.

Simeon Ball, Oriol Serra, Punctured combinatorial Nullstellensätze, Combinatorica, September 2009, Volume 29, Issue 5, pp 511–522

08.03.2018 16:15
Jakub Rówiński
On the 1/3–2/3 Conjecture

Let (P,≤) be a finite poset. For distinct elements x, y ∈ P , we define P(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0 ≤ α ≤ 1, we say (x,y) is an α-balanced pair 2 if α ≤ P(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. Proof of above conjecture as well as stronger condition of having a 1/2-balanced pair for certain families of posets will be shown. These include lattices such as the Boolean, set partition, subspace lattices and variety of diagrams.

Emily J. Olson, Bruce E. Sagan, On the 1/3--2/3 Conjecture, Order, 2018

01.03.2018 16:15
Bartłomiej Bosek
Some open problems
25.01.2018 16:15
Bartłomiej Bosek
News about Combinatorial Nullstellensatz

I will present some new theorems, proofs and open problems concerning about Combinatorial Nullstellensatz and related problems.

Terence Tao. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. arXiv:1310.6482 (2014), pp 1-44.

18.01.2018 16:15
Jarek Duda
Some nonstandard approaches to hard computational problems

I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm and the problem with global optimization formulations used in adiabatic quantum computers. Then show some perspectives on the subset-sum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem. Finally discuss the difficulty of the graph isomorphism problem on the most problematic cases: strongly regular graphs, and algebraic perspective on this problem.

Jarek Duda. Some unusualapproaches to hard computational problems. slides.

11.01.2018 16:15
Maciej Woźniak, Dawid Pyczek
Online Vertex Cover and Matching: Beating the Greedy Algorithm

Authors study the online vertex cover problem and online matching problem in bipartite graphs and in general graphs. For the case of bipartite graphs their result is optimal water-filling algorithm with competitive ratio 1/(1-1/e) . The main contribution of this paper is a 1.901-competitive algorithm for vertex cover in general graphs which beats the well-known trivial 2-competitive algorithm. The next major result is a primal-dual analysis of given algorithm that implies the dual result of a 0.526-competitive algorithm for online fractional matching in general graphs. On the hardness side authors show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs.

Yajun Wang, Sam Chiu-wai Wong. Online Vertex Cover and Matching: Beating the Greedy Algorithm. arXiv (2013), pp 1-21.

04.01.2018 16:15
Grzegorz Bukowiec
Feedback Vertex Set Problem

A Feedback Vertex Set (FVS) is a subset of vertices in a graph such that its removal results in an acyclic graph. The problem of finding a minimal FVS is one of the classic NP-complete problems. However, in some practical cases, we can assume that its size is fairly small. This motivated an intensive study of the parametrized version of this problem, which asks either for FVS of a size at most k or an information that it doesn't exist. There are several deterministic algorithms known which solve this in time O*(ck), the best one for now being O*(3.592k).

21.12.2017 16:15
Paweł Kubiak, Jakub Rówiński
Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms

On bipartite graphs, problem of constrained minimum vertex cover (MIN-CVCB) is defined as follows: given a bipartite graph G = (V, E) with vertex bipartition V = U ∪ L and two integers ku and kl, decide whether there is a minimum vertex cover in G with at most ku vertices in U and at most kl vertices in L. We show how it is related to practical problems. We prove that (MIN-CVCB) is NP-complete. However, there are many parametrized algorithms running in decent time. We describe one of them, whereby linear kernelization method it achieves O(1.26ku+kl +(ku +kl)|G|) time.

Jianer Chen, Iyad A.Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. Journal of Computer and System Sciences. Vol. 67, Iss. 4, (2003), pp. 833-847.

14.12.2017 17:00
Jakub Nowak
Dulmage–Mendelsohn Decomposition

In a graph G, let B be the set of vertices covered by every maximum matching in G, and let D = V(G) − B. Further partition B by letting A be the subset consisting of vertices with at least one neighbor outside B, and let C = B − A. The Gallai-Edmonds Decomposition of G is the partition of V(G) into the three sets A, C, D. The Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is an extension of the Gallai-Edmonds decomposition.

L. Lovász, M. D. Plummer. Matching theory. North-Holland Mathematics Studies, 121. Annals of Discrete Mathematics, 29. North-Holland Publishing Co., Amsterdam. 1986. pp. xxvii+544. ISBN: 0-444-87916-1. Chapter 4.3.

14.12.2017 16:15
Lev Deliatynskyi
A short proof of the Berge–Tutte Formula and the Gallai–Edmonds Structure Theorem

This paper studies the maximum matching in a graph. It shows a short proof of a Berge-Tutte formula and the Gallai-Endmonds structure theorem. Authors use Hall's theorem to prove it. Deficiency in a graph (def(S), S⊆V(G)) is o(G-S) - |S|, where o(G-S) is the number of odd components in G-S. Berge-Tutte formula says that the maximum size of a matching in an n-vertex graph G is 1/2(n-def(G)), where def(G) = maxS⊆V(G)def(S). Gallai Edmonds has a sharper formulation which gives considerable information about the structure of maximum size matchings.

Douglas B.West. A short proof of the Berge–Tutte Formula and the Gallai–Edmonds Structure Theorem. European Journal of Combinatorics. Vol. 32, Iss. 5, (2011), pp. 674-676.

07.12.2017 16:15
Jan Derbisz, Franciszek Stokowacki
On Low Rank-Width Colorings

We say that a class C of graphs admits low rank-width colorings if there exist functions N : N → N and Q: N → N such that for all p ∈ N, every graph G ∈ C can be vertex colored with at most N(p) colors such that the union of any i ≤ p color classes induces a subgraph of rank-width at most Q(i). It turns out that for every graph class C of bounded expansion and every positive integer r, the class {Gr : G ∈ C} of r-th powers of graphs from C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. Additionally, every graph class admitting low rank-width colorings is χ-bounded.

O-joung Kwon, Michał Pilipczuk, and Sebastian Siebertz. On Low Rank-Width Colorings. arXiv (2017), pp. 1-17.

30.11.2017 16:15
Krzysztof Maziarz, Tomasz Wesołowski
The Generalised Colouring Numbers on Classes of Bounded Expansion

We introduce two classes of graphs - graphs with bounded expansion and nowhere dense graphs. These notions are a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, to name just a few classes which are studied extensively in combinatorial and computer science contexts. We also present generalized colouring numbers admr(G), colr(G), and wcolr(G) and show important applications in the theory of above-mentioned classes of graphs. Finally, we prove that every graph excluding a fixed topological minor admits a universal order, that is, one order witnessing that the colouring numbers are small for every value of r, and show that it can be efficiently computed.

Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The Generalised Colouring Numbers on Classes of Bounded Expansion. In Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Vol. 58 (2016), pp. 85:1-85:13.

23.11.2017 16:15
Gabriel Jakóbczak
Majority coloring games

A vertex coloring of graph G satisfies the majority rule, if for each vertex v at most half of its neighbors receive the same color as v. A coloring which satisfies the majority rule is called majority coloring. We consider its game version. For given graph G and color set C two players, Alice and Bob, in alternating turns color vertices with respect to the majority rule. Alice wins when every vertex becomes colored, while goal for Bob is to create a vertex which cannot be colored with any color belonging to the set C without breaking the majority rule. Let µg(G) denote the least number of colors belonging to C for which Alice has winning strategy in game on graph G. We show that if the color set C is finite, there exists a graph G on which Bob has winning strategy. We prove also that for graphs with col(G) = 3 parameter µg(G) is still unbounded.

16.11.2017 16:15
Anna Kobak, Grzegorz Jurdziński
The Erdős discrepancy problem - Part II

Erdős discrepancy problem has waited for the solution for over 70 years until last year Terrence Tao, with a help of Polymath project, has published a paper with its solution. After having our friends given an introduction to the topic and shown the Fourier analytic reduction of the problem last week we will continue presenting the proof. It will include the proof of Elliot-type conjecture and a sketch of how to apply a generalised Borwein-Choi-Coons analysis for the final steps of the main proof.

Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2 (2016), pp. 1-20.

09.11.2017 16:15
Aleksandra Mędrek, Marcin Muszalski
The Erdős discrepancy problem - Part I

Erdős discrepancy problem had remained unresolved for more than 80 years. In 2015 Erdős theorem has been proofed by Terrence Tao. We present first part of his proof where he uses a Fourier-analytic reduction obtained as part of the Polymath5 project which reduces the problem to the case when f is replaced by a (stochastic) completely multiplicative function g.

Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2, (2016), pp. 1-20.

26.10.2017 16:15
Wojciech Kruk
Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching

We give a simple proof that the RANKING algorithm of Karp, Vazirani and Vazirani is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation.

Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg. Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 101-107, SIAM, Philadelphia, PA, 2012.

19.10.2017 16:15
Sylwester Klocek
On-line bipartite matching made simple

We examine the classic on-line bipartite matching problem studied by Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. Algorithm attempts to match online new vertices with edges. Such a decision, once made, is irrevocable. The objective is to maximize the size of the resulting matching. We will see a sketch of simple proof of their result that the Ranking algorithm for this problem achieves a competitive ratio of 1 − 1/e.

B.E. Birnbaum, C. Mathieu. On-line bipartite matching made simple. SIGACT News 39 (1), 80-87, 2008.

12.10.2017 16:15
Zygmunt Łenyk
Handwritten graph diagrams recognition
Graph visualisation problem is well known and there are many solutions to it. The reverse process - graph recognition - has been disregarded so far. Such solution has wide applications - from scientific to didactic. This paper focuses on hand-written graphs. Objects do not necessarily have regular shapes and there might be a lot of noise. Using computer vision techniques, we recognize first vertices and then edges. The result of the algorithm is a list of edges and a generated graph visualisation.
05.10.2017 16:15
Szymon Borak
On some problems in planar graphs

We give insight into competitive reachability for outerplanar graphs and also for other classes of graphs with bounded degree. Competitive reachability is a game where two players orient the edges of undirected graph G alternately until all edges of G have been oriented. One player wants to minimize the number of ordered pairs of distinct vertices (x, y) with a directed path from x to y. And the second want to maximize it.

Furthermore we focus on harmonious coloring conjecture for outerplanar graphs and further attempts in this area. A harmonious coloring of a graph G is a proper vertex coloring of G in which every pair of colors appears on adjacent vertices at most once. The harmonious chromatic number, denoted by h(G), is the minimum number of colors in a harmonious coloring. Analogically we define  harmonious edge coloring in which every pair of colors appears on incident edges at most once. The minimal number of color we denote by h'(G). The conjecture states that h(G)<=h'(G).

Finally we tackle the hamiltonian cycles in grid graphs. Grid graph are finite vertex induced subsets of infinite lattice, composed from unit-side squares, equilateral triangles or equilateral hexagons. Decide whether the grid graph has hamiltonian cycle is NP-hard in general.

01.06.2017 16:15
Wojciech Kruk, Piotr Kruk
Ulam Sequences and Ulam Sets
The Ulam sequence is given by a1=1,a2=2, and then, for n≥3, the element an is defined as the smallest integer that can be written as the sum of two distinct earlier elements in a unique way. This gives the sequence 1,2,3,4,6,8,11,13,16,…, which has a mysterious quasi-periodic behavior that is not understood. Ulam's definition naturally extends to higher dimensions: for a set of initial vectors {v1,…,vk}⊂ℝn, we define a sequence by repeatedly adding the smallest elements that can be uniquely written as the sum of two distinct vectors already in the set. The resulting sets have very rich structure that turns out to be universal for many commuting binary operations. We give examples of different types of behavior, prove several universality results, and describe new unexplained phenomena.
25.05.2017 16:15
Sylwester Klocek, Maciej Woźniak
On the complexity of the chip-firing reachability problem
In this paper, we study the complexity of the chip-firing reachability problem. We show that for Eulerian digraphs, the reachability problem can be decided in polynomial time, even if the digraph has multiple edges. We also show a special case when the reachability problem can be decided in polynomial time for general digraphs: if the target distribution is recurrent restricted to each strongly connected component. Both of these algorithms are strongly polynomial. As a further positive result, we show that the chip-firing reachability problem is in co-NP for general digraphs. We also show that the chip-firing halting problem is in co-NP for Eulerian digraph
18.05.2017 16:15
Katrzyna Janocha
Proper Orientations of Planar Bipartite Graphs
An orientation of a graph G is proper if any two adjacent vertices have different indegrees. The proper orientation number χ (G) of a graph G is the minimum of the maximum indegree, taken over all proper orientations of G. In this paper, we show that a connected bipartite graph may be properly oriented even if we are only allowed to control the orientation of a specific set of edges, namely, the edges of a spanning tree and all the edges incident to one of its leaves. As a consequence of this result, we prove that 3-connected planar bipartite graphs have proper orientation number at most 6. Additionally, we give a short proof that χ (G) ≤ 4, when G is a tree and this proof leads to a polynomial-time algorithm to proper orient trees within this bound.
11.05.2017 16:15
Anna Kobak
Lambda number for the direct product of some family of graphs
An L(2,1) labeling for a graph G = (V,E) is a function f on V such that | f(u) - f(v)| >= 2 if u,v are adjacent and f(u), f(v) are distinct if u,v are vertices of distance two. The lambda(G) for G is the minimum span over all L(2,1) labelings of G. We will show that when m>=6 and n>=3, lambda(Pm x Cn) = 7 if and only if n is not a multiple of 7 and also provide the conditions on m and n such that lambda(Cm x Cn) <= 7.
04.05.2017 16:15
Grzegorz Bukowiec
Even factors of graphs
An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. It has been shown that if a graph G has an even factor, it also has an even factor F such that |E(F)| >= 4/7 (|E(G)| + 1). 4/7 is the best possible ratio here, but we will try to strengthen this lower bound by taking the set of vertices of degree 2 into consideration.
27.04.2017 16:15
Jakub Szarawski
A greedy approach to the Turtle Tower problem
In the Turtle Tower problem we are given n turtles with a mass and capacity for each of them. We are looking for the highest tower possible, regarding that capacity of every turtle in the tower cannot be exeeded by the sum of the masses of turles it carry. Presented solution is faster than commonly known dynamic one.
20.04.2017 16:15
Helena Borak, Zygmunt Łenyk
Necklaces, Convolutions, and X + Y, A new upper bound for the online square packing
Necklaces, Convolutions, and X + Y

The necklace alignment problem is to find the optimal rotation of the necklaces to best align the beads, when we have two necklaces given, each with n beads at arbitrary positions. Alignment is measured according to the ℓ_p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p = 1, p even, and p = ∞ and how these problems can be reduced to convolution problems which can be solve in subquadratic time. Besides, we say how the necklace alignment problems, and their corresponding convolution problems, are also intrinsically connected to problems on X + Y matrices.

A new upper bound for the online square packing

In online square packing problem we try to minimise the height of squares on a plane with width 1. Squares come one by one, they can’t overlap and once set, it’s position can’t be changed. A new upper bound (ratio between algorithm result and optimal packing) is found by applying modified version of previously used First Fit Shelf algorithm.
06.04.2017 16:15
Andrzej Głuszyński, Jakub Nowak
Local Antimagic Vertex Coloring of a Graph, A short proof of Cayley's tree formula
Local Antimagic Vertex Coloring of a Graph

The edge labelling is called 'local antimagic', if for all vertices sum of labels for incident edges is different for every two adjacent vertices. Such sum induce a correct vertex colouring. The local antimagic chromatic number - X_la(G) - is the minimum number of colours used by any proper local antimagic labelling. In the paper authors present results on this parameter for trees, friendship, wheel and clique graphs.

A short proof of Cayley's tree formula

Cayley’s tree formula is a very elegant result in Graph Theory. The problem is to find the number of all possible trees on a given set of labeled vertices. For n = 2 and vertex set {v1, v2}, we have only one tree. For n = 3 and vertex set {v1, v2, v3}, we have 3 different trees. Similarly for n = 4, we have 16 trees. We give a short proof of Cayley’s tree formula for counting the number of different labeled trees on n vertices.

Alok Bhushan Shukla, A short proof of Cayley's tree formula.
23.03.2017 16:15
Aleksandra Mędrek, Marcin Muszalski
Planning for Fast Connectivity Updates
Understanding how a single edge deletion can affect the connectivity of a graph amounts to finding the graph bridges. But when faced with d > 1 deletions, can we establish as easily how the connectivity changes? When planning for an emergency, we want to understand the structure of our network ahead of time, and respond swiftly when an emergency actually happens. We describe a linear-space representation of graphs which enables us to determine how a batch of edge updates can impact the graph. Given a set of d edge updates, in time O(d polylg n) we can obtain the number of connected components, the size of each component, and a fast oracle for answering connectivity queries in the updated graph. The initial representation is polynomial-time constructible.
  1. Mihai Patrascu , Mikkel Thorup, Planning for Fast Connectivity Updates, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.263-271, October 21-23, 2007
16.03.2017 16:15
Patryk Urbański
Generating Linear Extensions Fast

One of the most important sets associated with a poset P is its set of linear extensions, E(P). In this paper, we present an algorithm to generate all of the linear extensions of a poset in constant amortized time; that is, in time O(e(P)), where e(P) = |E(P)|. The fastest previously known algorithm for generating the linear extensions of a poset runs in time O(n*e(P)), where n is the number of elements of the poset. Our algorithm is the first constant amortized time algorithm for generating a ``naturally defined'' class of combinatorial objects for which the corresponding counting problem is #P-complete. Furthermore, we show that linear extensions can be generated in constant amortized time where each extension differs from its predecessor by one or two adjacent transpositions. The algorithm is practical and can be modified to efficiently count linear extensions, and to compute P(x < y), for all pairs x,y, in time O(n^2 + e(P)).

Gara Pruesse, Frank Ruskey. Generating Linear Extensions Fast. SIAM J. Comput. Vol. 23, No. 2 (1994), pp. 373-386.

09.03.2017 16:15
Grzegorz Matecki
Boolean dimension of posets
A boolean dimension bdim(P) of a poset P=(X,<) is a smallest number k for which there is a set l1, l2, ..., lk of labelings X:->N and a boolean formula f(a1, ..., ak) such that the following is true: x < y in P iff f(a1, .., a_k) = 1 where ai =1 iff li(x) < li(x).
Generally, it is simple to observe that bdim(P) <= dim(P). Also, it is known that there is a constant c such that bdim(n) <= c log(n) for any poset P of size n.
The are few interesting open problems for boolean dimension:
1) Is boolean dimension of the boolean lattice of size n less that n?
2) Is there a constant c such that bdim(P) < c for any planar poset P?
09.03.2017 16:15
Mateusz Twaróg, Łukasz Majcher
Combinatorial library core
Presentation and discussion on core functionalities of the c++ combinatorial library. introduction to classes representing graphs, graph traversing algorithm templates and simple GUI.
26.01.2017 16:15
Wojciech Kruk, Maciej Woźniak
A few open problems
We mentioned the following open problems in graph theory and discrepancy theory:

1. Erdos discrepancy problem
2. Hoang - Reed conjecture
3. Seagull problem - a consequence of Hadwiger's conjecture
Paweł Petecki
Akademia Górniczo-Hutnicza
Symmetry breaking polynomial
Let G be a graph, and let Γ= Aut G. A coloring c of G is symmetry-breaking if for every non-identity automorphism φ in Γ, there is some vertex v of G such that c(v)≠c(φ(v)). There has been a lot of work on the minimum number of colors in a symmetry-breaking coloring of G. We discuss here a different problem: counting the number of k-colorings that are symmetry breaking. The tool, as is frequently the case for problems such as this one, is Möbius inversion. To solve this problem we define symmetry breaking polynomial ψG. For positive integer k (number of colors), ψG(k) is the number of k-colorings that break all non-trivial symmetries of the graph G.
22.12.2016 16:15
Łukasz Majcher, Jan Szczepaniec
Convex p-partitions of bipartite graphs
A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p ≥ 1, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.
Anna Kobak
Open problems in graph theory concerning minors.
We mentioned following open problems in graph theory:
  1. Hadwiger's Conjecture
  2. Seagull Conjecture
  3. Jorgensen's Conjecture
  4. Unfriendly partitions
  5. and a few more conjectures concerning minors.
Zygmunt Łenyk
Rendezvous on the line.
This is one of a handful of rendezvous problems where two players must find one another in a certain structured domain. In line case, players are placed on the line with distance 2, without knowing neither on which side is their partner, nor the direction of the line. I'll concentrate on the symmetric case where players must follow a specific (but maybe mixed) strategy. The conjecture is that best expected time of meeting two players equals 4.25.
  3. www.openproblemgarden.org/op/rendezvous_on_a_line
  4. Improved bounds for the symmetric rendezvous value on the line. Qiaoming Han, Donglei Du, Juan Vera, Luis F. Zuluaga. SODA 2007
Patryk Urbański
Coloring Ordinary Maps, Maps of Empires and Maps of the Moon
A short review of generalized map coloring problems:
  • Heawood's empire coloring problem in the plane - 6M colors are sufficient to color a map of empires each consisting of at most M connected regions.
  • Earth-Moon map coloring Mathematics Magazine Vol. 66, No. 4 (Oct., 1993), pp. 211-226problem - it is known that the chromatic number of thickness-2 graphs is between 9 and 12. It is an open problem to find the exact value.
Coloring Ordinary Maps, Maps of Emipres, and Maps of the Moon. Joan P. Hutchinson. Mathematics Magazine. Vol. 66, No. 4 (Oct., 1993), pp. 211-226.
Wojciech Łopata
Several open problems from game theory, graph theory and combinatorics.

I'll briefly introduce the audience to two unrelated areas: book embedding and mechanism design, and walk through some open problems in those areas.
Wikipedia: Book embedding
Wikipedia: Mechanism design

Paweł Kubiak
Succinct Data Structures
Grzegorz Bukowiec
On more variants of the Majority Problem
Gabriel Jakóbczak
Proper orientations of some types of graphs
Let G be a simple graph. We say that orientation of graph G is proper if for every pair of adjacent veritces u and v their indegrees are different. It was proved by Mieczysław Borowiecki, Jarosław Grytczuk and Monika Pilśniak that for every simple graph exists its proper orientation. Now we can define the proper orientation number of graph G as the minimum of the maximum indegree, taken over all proper orientations of G. We show that for some classes of bipartite graphs their proper orientation number is less than or equal to 6. We also show that this parameter is at most 4 for graphs which are trees and proof of that fact leads to a polynomial-time algorithm of finding proper orientation of such graphs.

Fiachra Knox, Sebastián González Hermosillo de la Maza, Bojan Mohar, and Cláudia Linhares Sales. 
Proper Orientations of Planar Bipartite Graphs. 
pages 2-6, sep 2016.
Magdalena Gargas
The geometry of nesting problems: A tutorial
Helena Borak
Exact algorithms for the two-dimensional strip packing problem with and without rotations
We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90 degree rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP, wherein all given rectangles are required to be packed without wasted space, and design branch-and-bound algorithms introducing several branching rules and bounding operations. A combination of these rules yields an algorithm that is especially efficient for feasible instances of PP. We then propose several methods of applying the PP algorithms to 2SP. Our algorithms succeed in efficiently solving benchmark instances of PP with up to 500 rectangles and those of 2SP with up to 200 rectangles. They are often faster than existing exact algorithms specially tailored for problems without rotations.
Krzysztof Barański
Level-Oriented Two-Dimensional Packing Algorithms
The paper includes an overview of several algorithms, their complexities and approximation ratios solving two-dimensional strip packing problem:
1) First-Fit Decreasing Height (FFDH) - time complexity: O(nlgn), approximation ratio: <= 17/10 OPT(I) + 1 [with proof]
2) Next-Fit Decreasing Height (NFDH) - time complexity: O(nlgn), approximation ratio: <= 17/10 OPT(I) + 1 [with proof]
3) Best-Fit Decreasing Height (BFDH), Bottom-Left (BL), Steinberg's algorithm, Split-Fit (SF)
Bartłomiej Bosek
A new variant of the game of cops and robber

The talk presents a joint work of Jarosław Grytczuk, Joanna Sokół, Małgorzata Śleszyńska-Nowak. We consider the following metric version of the Cops and Robbers game. Let G be a simple graph and let k≥1 be a fixed integer. In the first round, Cop picks a subset of k vertices B={v1,v2,…,vk} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector Du(B)=(d1,d2,…,dk) whose components di=dG(u,vi), i=1,2,…,k, are the distances from u to the vertices of B. In the second round, Robber may stay at the vertex u or move to any neighbouring vertex which is kept in a secret. Then Cop picks another k vertices and asks as before for the corresponding distances to the vertex occupied by Robber. And so on in every next round. The game stops when Cop determines exactly the current position of Robber. In that case, she is the winner. Otherwise, Robber is the winner (that is if Cop is not able to localize him in any finite number of rounds). Let ζ(G) denote the least integer k for which Cop has a winning strategy. Notice that this parameter is well defined since the inequality ζ(G)≤|V(G)| holds obviously.

Michał Dyrek
The Linear Arboricity of Graphs
A linear forest is a forest in which each connected component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests whose union is the set of all edges of G. The linear arboricity conjecture asserts that for every simple graph G with maximum degree D, la(G) <= [(D+1)/2].
Although this conjecture received a considerable amount of attention, it has been proven only for D <= 6, D = 8, D = 10 and the best known general upper bound for la(G) is la(G) <= [3D/5] for even D and la(G) <= [(3D + 2)/5] for odd A. Here we prove that for every e > 0 there is a D_0 so that for every G with maximum degree D > D_0, la(G) <= (1/2 + e) * D. To do this, we first prove the conjecture for every G with an even maximum degree D and with girth g > 50*D.
Pola Kyzioł
Matching in regular and almost regular graphs

I present an O(n^2*log n)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(r*n^2*log n) time if the difference between the maximum degree and the minimum degree is less than r.

R. Yuster, Maximum matching in regular and almost regular graphs

Piotr Bejda
Perfect matchings in O(n log n) time in regular bipartite graphs

In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bi-partite graph on 2n nodes with m=nd edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m*sqrt(n)). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost and Schirra). In a recent line of work by Goel, Kapralov and Khanna the O(m) time algorithm was improved first to O'(min(m, n^2.5/d)) and then to O'(min(m,n^2/d)). It was also shown that the latter algorithm is optimal up to polylogarithmic factors among all algorithms that use non-adaptive uniform sampling to reduce the size of the graph as a first step.
In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, an d is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. We also show that randomization is crucial for obtaining o(nd) time algorithms by establishing an Ω(nd) lower bound for any deterministic algorithm. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time O(n log2 n) time, with O(m) pre-processing time; this gives a simple O(m + mn log2 n) time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix.

A. Goel and M. Kapralov and S. Khanna, Perfect matchings in O n log n time in regular bipartite graphs

Krzysztof Kleiner
Online Dual Edge Coloring of Paths and Trees

Extending the results presented on the preceding seminar, we study a dual version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k, of available colors. All of our results are with regard to competitive analysis. For paths, we consider k=2, and for trees, we consider any k>=2. We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms on paths as well as trees. This is the first time that an optimal algorithm for online dual edge coloring has been identified for a class of graphs. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. Again, it is the first time that this has been done for a class of graphs. For trees, we also show that even randomized algorithms cannot be much better than First-Fit.

L. M. Favrholdt, J. W. Mikkelsen, Online Dual Edge Coloring of Paths and Trees

Mateusz Twaróg
On-Line Edge-Coloring with a Fixed Number of Colors

We investigate a variant of on-line edge-coloring in which there is a fixed number of colors available and the aim is to color as many edges as possible. We prove upper and lower bounds on the performance of different classes of algorithms for the problem. Moreover, we determine the performance of two specific algorithms, First-Fit and Next-Fit. Specifically, algorithms that never reject edges that they are able to color are called fair algorithms. We consider the four combinations of fair/not fair and deterministic/randomized. We show that the competitive ratio of deterministic fair algorithms can vary only between approximately 0.4641 and 1/2 , and that Next-Fit is worst possible among fair algorithms. Moreover, we show that no algorithm is better than 4/7 -competitive. If the graphs are all k-colorable, any fair algorithm is at least 1/2 -competitive. Again, this performance is matched by Next-Fit while the competitive ratio for First-Fit is shown to be k/(2k - 1), which is significantly better, as long as k is not too large.

M. Favrholdt, N. Nielsen, On-Line Edge-Coloring with a Fixed Number of Colors, Algorithimca 35 (2), 176-191, 2003

Helena Borak
Linear Extensions of N-free Orders

We consider the number of linear extensions of an N-free order P. We give upper and lower bounds on this number in terms of parameters of the corresponding arc diagram. We propose a dynamic programming algorithm to calculate the number. The algorithm is polynomial if a new parameter called activity is bounded by a constant. The activity can be bounded in terms of parameters of the arc diagram.

Stefan Felsner , Thibault Manneville, Linear Extensions of N-free Orders, Order 32 (2), 147-155, 2015

Leszek Jakub Kania
Improved Bounds for Online Preemptive Matching

When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight.  The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms.

L. Epstein, A. Levin, D. Segev, O. Weimann, Online Preemptive Matching, arXiv 2012

Jakub Cieśla
Computing Tree-Depth Faster Than 2^n

A connected graph has tree-depth at most k if it is a subgraph of the clusure of a rooted tree whose height is at most k. The autors give an algorithm which for a given n-vertex graph G, in time O(1.9602^n) computes the tree-depth of G. The algorithm is based on combinatorial results revealing the structure of minimal rooted trees whose closures contain G.

F. V. Fomin, A. C. Giannopoulou, M. Pilipczuk, Computing Tree-Depth Faster Than 2^n, Algorithmica 73 (1), 202-216, 2015

Karol Banyś
Fast Algorithm for Partial Covers in Words

In this article autors introduce a new notion of α-partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least α positions in w. They develop a data structure of O(n) size (where n=|w|) that can be constructed in O(nlogn) time which they apply to compute all shortest α-partial covers for a given α. They also employ it for an O(nlogn)-time algorithm computing a shortest α-partial cover for each α=1,2,…,n.

Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski , Wojciech Rytter, Tomasz Waleń, Fast Algorithm for Partial Covers in Words, Algorithmica 73 (1), 217-233, 2015

Paweł Kubiak
Lower bounds for dynamic algorithms

In my presentation I will discus some elementary dynamic problems (Single source reachability and Dynamic diameter) and then I will present interesting reduction from this problems to Orthogonal Vectors Problems. These reductions imply that if it would be possible to solve SSR in O(m^(1-ε)) or do 1.3 approximation of DD in O(m^(2-ε)) then SETH will be refuted.

Amir Abboud, Popular Conjectures and Dynamic Problems, 2015

Katarzyna Janocha
Conditional hardness and equivalences for graph problems

Some graph problems (such as such as APSP, negative triangle, distance product or radius) do not have any known solutions better then the naive ones. We show subquadraic and subcubic reductions between them, proving that in case of finding a faster algorithm for any of the problems would be equivalent of reducing the complexity of each of them. We separate algorithms for sparse and dense graphs and focus on basic methods for both classes.

V. Williams, Conditional hardness and equivalences for graph problems

Zygmunt Łenyk
Hardness for Easy Problems (overview)

Introduction into a young branch of algorithmics. We discuss why we are stuck during developing fast algorithms to some well-known problems. Problems in P and suitable reductions form equivalence classes of problems, inside which improving asymptotic time of any of them would automatically improve the rest. At the bottom of these classes lie problems such as: 3SUM, all-pairs-shortest-paths, orthogonal vectors. Their complexities are guarded by strong conjectures which, if proven wrong, would revoke widely believed conjectures such as SETH.  

Amir Abboud, Arturs Backurs, Piotr Indyk and Virginia V. Williams, Hardness for easy problems - An introduction, 2015

Maciej Poleski
An online version of Rota's basis conjecture
Rota's basis conjecture states that in any square array of vectors whose rows are bases of a fixed vector space the vectors can be rearranged within their rows in such a way that afterwards not only the rows are bases, but also the columns. We discuss an online version of this conjecture, in which the permutation used for rearranging the vectors in a given row must be determined without knowledge of the vectors further down the array. The paper contains surprises both for those who believe this online basis conjecture at first glance, and for those who disbelieve it.  
Guus P. Bollen, Jan Draisma, An online version of Rota's basis conjecture, Journal of Algebraic Combinatorics, October 2014
Helena Borak
Variants of Hat Guessing Games
Hat problems have become a popular topic in recreational mathematics. In a typical hat problem, each of n players tries to guess the color of the hat they are wearing by looking at the colors of the hats worn by some of the other players. In this paper we consider several variants of the problem, united by the common theme that the guessing strategies are required to be deterministic and the objective is to maximize the number of correct answers in the worst case. We also summarize what is currently known about the worst-case analysis of deterministic hat-guessing problems with a finite number of players.  
S.Butler, M.T.Hajiaghayi, R.D.Kleinberg, T.Leighton, Hat Guessing Games
Marcin Dziaduś
Five-list-coloring of planar graphs
Let G be a plane graph with outer cycle C, let u,v be vertices of C and let (L(x):x in V(G)) be a family of sets such that |L(u)|=|L(v)|=2, L(x) has at least three elements for every vertex x of C \ {u,v} and L(x) has at least five elements for every vertex x of G \ V(C). We prove a conjecture of Hutchinson that G has a proper coloring f such that f(x) belongs to L(x) for every vertex x of G.  
Luke Postle, Robin Thomas, Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs, Journal of Combinatorial Theory, Series B
Karol Banyś
Online Load Balancing and Correlated Randomness
This paper looks at online load balancing, in a setting where each job can only be served by a subset of the servers. The subsets are revealed only on arrival, and can be arbitrary. The cost of an allocation is the sum of cost for each server, which in turn is a convex increasing function of the number of jobs allocated to it. There are no departures.  
S. Moharir, S. Sanghavi. Online Load Balancing and Correlated Randomness. 50th Annual Allerton Conference, 2012
U. Vazirani V. Vazirani A. Mehta, A. Saberi. Adwords and generalized on-line matching. Proceedings of FOCS, 2005
Andrzej Dorobisz
Random Walks that Find Perfect Objects and the Lov´asz Local Lemma
We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lov´asz Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that algorithmic progress is measured in terms of entropy rather than energy (number of violated constraints) so that termination can be established even under the proliferation of states in which every step of the algorithm (random walk) increases the total number of violated constraints.  
Dimitris Achlioptas, Fotis Iliopoulos, Random Walks that Find Perfect Objects and the Lovasz Local Lemma, FOCS 2014
18.11.2014,Jakub Brzeski
Markov Chains and Random Walks on Graphs
D. Aldous and J. A. Fill, Reversible Markov Chains and Random Walks on Graphs, monograph, 2014.
L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 353–397, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
Jakub Cieśla
Finding All Maximally-Matchable Edges in a Bipartite Graph
We consider the problem of finding all maximally-matchable edges in a bipartite graph G = (V, E), i.e., all edges that are included in some maximum matching. We show that given any maximum matching in the graph, it is possible to perform this computation in linear time O(n + m) (where n = |V| and m = |E|). Hence, the time complexity of finding all maximally-matchable edges reduces to that of finding a single maximum matching.  
T. Tassa, Finding all maximally-matchable edges in a bipartite graph, Theoret. Comput. Sci. 423 (2012), 50–58.
Marcin Ziemiński
Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs
In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. We also show that randomization is crucial for obtaining o(nd) time algorithms by establishing an (nd) lower bound for any deterministic algorithm.  
A. Goel, M. Kapralov, S. Khanna, Perfect matchings in O(n log n) time in regular bipartite graphs, Proceedings of the 2010 ACM International Symposium on Theory of Computing (STOC'10), 39–46, ACM, New Yo
Patryk Mikos
Maximum Matching in Regular and Almost Regular Graphs
An O(n^2*log(n))-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(r*n^2 log n) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in O(√nm)-time for graphs with m edges, whenever m = ω(rn1.5 log n).  
R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66 (2013), no. 1, 87–92.
07.10.2014,Bartłomiej Bosek
Incremental algorithm on bipartite graphs
The talk presents the jont work of Bartłomiej Bosek, Darek Leniowski, Piotr Sankowski, and Anna Zych. We investigated the problem of maintaining maximum size matchings in incremental bipartite graphs. In this problem a bipartite graph G between n clients and n servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i.e., after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation.  
Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych. Online bipartite matching in offline time. In Proceedings of the 55th Symposium on Foundations of Computer Science, FOCS14, pp. 384-393, 2014.