Algorithmics Research Group

Theoretical Computer Science
Faculty of Mathematics and Computer Science
Jagiellonian University

Theoretical Computer Science Seminar

Wednesday: 16:15 - 18:00, room 117

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.

table edited by: Iwona Cieślik

11.06.2008, Zbigniew Lonc Politechnika 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 Pikhurko Carnegie 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ński University 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 Nesetril Charles 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 Bartnicki University 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(nnm) time and O(nm) space using a simple dynamic programming technique. In 2004 I-Husan Yang proposed an O(nm)-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ůma Charles University, Prague	Recovering ENIGMA, the cipher system

09.01.2008, Marek Chrobak University 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 Barto Eduard Č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-Oppenheim Simon 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ńska UAM	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

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 Kierstead Arizona 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 classiﬁcation 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

01.07.2005, Nobu-Yuki Suzuki, Shizuoka University, Japan	Epistemic logic and game theory
	A brief overview of epistemic logics and their game-theoretical applications is given. This interdisciplinary field has many aspects arising from various research lines. In this talk, I give an outline of the recent developments of epistemic-logical approach to decision making process in game-theoretical situations.
01.06.2005, Grzegorz Łukasik	Mobile Robots Contests
	Mobile Robots Contests organized by Computer Science and Technology University is presented: rules of the contest, the problems that students were solving and intresting solutions that were implemented. The first three places were taken by teams from Jagiellonian University.
	references: Contest home page: http://www.best.agh.edu.pl/konkurs/
18.05.2005, Michael Sołtys, McMaster University, Hamilton, ON, Canada	P vs NP
	The "P vs NP" problem is a central problem of theoretical computer science, and indeed of mathematics (it was named one of the seven Millennium Problem by the Clay Mathematical Institute, and there is a one million dollar prize for a solution: http://www.claymath.org/millennium). Despite thirty years of intense efforts, we are not near a solution, and we do not have promising techniques to tackle this problem. For example, since diagonal arguments "relativize", they will probably not work in this case. Exponential lower bounds on Boolean circuits are also hopelessly difficult to obtain. De-randomizing turns out to be just as difficult as separating P and NP. Cook proposed an attack based on a program of finding lower bounds for stronger and stronger propositional proof systems, building a repertoire of techniques and lower bounds, and ultimately showing that no polynomially bounded propositional proof system exists. The consequence of that would be that NP is not equal to coNP, and thus P is not equal to NP. In this talk, I will concentrate on this line of attack.
16.05.2005, 11.05.2005, Lech Palmowski	Seventeen lines and one-hundred-and-one points
	A curious problem from additive number theory is investigated: Given two positive integers S, Q, does there exist a sequence of positive integers that add up to S and whose squares add up to Q? We show that this problem can be solved in time polynomially bounded in the logarithms of S and Q. As a consequence, also the following question can be answered in polynomial time: For given numbers n and m, do there exist n lines in the Euclidean plane with exactly m points of intersection?
	references: G. J. Woeginger, Seventeen lines and one-hundred-and-one points, Theoretical Computer Science 321 (2004), 415-421
04.05.2005, 27.04.2005, Grzegorz Gutowski	Computational aspects of the 2-dimension of partially ordered sets
	A well-known method to represent a partially ordered set consists in associating to each element of P a subset of a fixed set S={1,..,k} such that the order relation coincides with subset inclusion. Given an order P, minimizing the size of the encoding, i.e. the cardinal of S, is however a difficult problem. The smallest size is called the 2-dimension of P. The paper details a proof that computing 2-dimension of a given poset is NPC. Reduction allows to prove the non-approximability of the problem. Later on the complexity of the 2-dimension for the class of trees is investigated. Authors present a 4-approximation algorithm for this class.
	references: M. Habibb, L. Nourinea, O. Raynauda and E. Thierry, Computational aspects of the 2-dimension of partially ordered sets, Theoretical Computer Science 312 (2004), 401-431
20.04.2005, 30.03.2005, Grzegorz Herman	The Complexity of Random Ordered Structure
	One of the ways of expressing the complexity of a structure is the minimal "depth" of quantifiers in a formula that describes it. The presented paper discusses such complexity of two types of structures. The authors prove that the complexity of a random bit string is O(loglogn), with high probability, and the complexity of an ordered random graph - Theta(log*n), with high probability.
	references: J.H. Spencer, K.St.John , The Complexity of Random Ordered Structure
23.03.2005, Mikołaj Zalewski	On-line Ramsey Theory
	The Ramsey game is played on an unbounded set of vertices by two players, called Builder and Painter. In one move Builder introduces a new edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monchromatic copy of a fixed target graph H, keeping the constructed graph in a prescribed class G. The main problem is to recognize the winner for a given pair H, G. In particular, authors of paper prove that Builder has a winning strategy for any k-colorable graph H in the game played on k-colorable graphs. Another class of graphs with this strange self-unavoidability property is the class of forests. They show that the class of outerplanar graphs does not have this proberty. The question of whether planar graphs are self-unaviodable is left open.
	references: J.A. Grytczuk, M. Haluszczak, H.A.Kierstead, On-line Ramsey Theory, The Elektronic Journal of Combinatorics 11(1), 2004
09.03.2005, Wiktor Żelazny	Online Algorithms for Market Clearing
	Randomized on-line algorithms that maximalize profit and liquidity of marketplace are presented. They work by finding a maximal set with perfect matching in subgraph of bid history graph - before incoming intervals are applied, some of them (or some of graph edges from incoming vertices) are removed, based at random criteria. Proof that estimated profit produced by optimal algorithm cannot be greater then estimated profit of presented algorithm was also shown.
	references: A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscript (2002)
01.03.2005, Wiktor Żelazny	Online Algorithms for Market Clearing
	This talk presents an online algorithm able to find maximal set W of vertexes of n-interval graph, such that a perfect matching exists on W. The alghoritm works on interval representation of graph and new intervals must be introduced in legal way (described in previous talk) for it to work, but it's competitive ratio is equal 1. Proof of alghoritm's optimality was presented.
	references: A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscript (2002)
23.02.2005, Jacek Krzaczkowski	Counting solutions of equations over two-element algebras.
	I refered my results connected with counting solutions of equations and systems of equations over fixed two-element algebra. It came out that the computational complexity of these problems depends only on termal clone of the algebra. I presented the classification of the computational complexity of the problems mentioned above.
26.01.2005, Wiktor Żelazny	Online Algorithms for Market Clearing
	A n-interval graph is created from interval graph by painting it's vertexes with n colours and removing all edges between vertices of the same colour. This talk introduced n-interval graphs, as well as the way their interval representation can represent history of buy and sell bids on exchange auction. Objectives of maximalizing marketplace's profit and liquidity are formulated as online problems, as new intervals are being introduced every time a new bid appears. A way of legal introduction of new intervals, corresponding to apperance of new bids, is described.
	references: A. Blum, T. Sandholm, M. Zinkevich, Online Alghoritms for Market Clearing, manuscipt (2002)
12.01.2005, Grzegorz Gronkowski	A boolean function requiring 3n network size.
	First part of talk contains a simple proof, that there exist functions with a nonlinear lower bound for the network complexity. The proof is based on a counting method. Afterwards I present Norbert Bloom's result, who defined n-ary boolean function with a 3n lower bound. The proof shows, that 3n-3 is a minimal number of logic gates which is necessary for computing this function.
	references: Norbert Bloom, A boolean function requiring 3n network size.
05.01.2005, T. Krawczyk, E. Szczypka	Comparability graphs.
	A graph G=(V,E) is a comparability graph if there exists a partial order (V,<) such that there exists an edge between vertices v and w iff either v < w or w < v. In our talk we presented a polynomial time algorithm (the best known that solves a similar problem - Spinrad, McConnell - has a complexity O(n+m)) for deciding whether a given graph G=(V,E) is a comparability graph. In our method we investigated relations that exist between sets of neighborhoods in comparability graphs.
15.12.2004, Marek Kwiatkowski	Dr. Frankenstein's Approach to On-line Algorithms
	Let A1...An be on-line algorithms for a problem P, competitive over subsets I1...In of inputs respectively. In this talk we show that under certain assumptions on P and I1...In it is possible to give an on-line algorithm for P that is competitive over all possible inputs. Two solutions are given: for deterministic and randomized algorithms.
	references: Yossi Azar, Andrei Z. Broder, Mark S. Manasse "Dr. Frankenstein's Approach to On-line Algorithms" (extended abstract)
08.12.2004, Krzysztof Maczyński	P-time algorithm for tree decomposition
	In my talk I presented a polynomial time algorithm for deciding whether a given tree is arbitrarily vertex decomposable (AVD) in a limited sense concerning no more than a constant number of components and if so, constructing one of possibly exponentially many such decompositions. I also assumed a constant bound on the maximal degree of the tree but this condition was shown to be unnecessary by a slight modification to my algorithm proposed by Mikołaj Zalewski. Additionally I detailed a construction of a maximally long greedy sequence over a set of colours whose cardinality is given. I characterized all sequences of equal length, proved that no longer ones exist and explicited a cubic function computing the length from the number of colours allowed.
01.12.2004, Jan Jeżabek	Graphs with high girth and high chromatic number
	This talk introduces a basic tool of the probabilistic method - the first moment method. The method is illustrated with an application to satisfiability problems. A simple theorem is presented stating that any instance of k-SAT with fewer than 2^k clauses is satisfiable. The first moment method is then used to prove that for every g, k >= 1 there exist graphs with no cycles of size g and with chromatic number greater than k.
	references: M.Molloy, The Probabilistic Method, in: M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, Probabilistic Methods for Algorithmic Discrete Mathematics, Springer 1998
24.11.2004, Piotr Micek	Natural algorithm for Online Chain Covering of Upgrowing Interval Posets
	We have already proven that a competitive ratio for Online Chain Covering of Upgrowing Posets is equal to 2. At this talk I present a simple online algorithm which has optimal competitive ratio.
17.11.2004, 10.11.2004, Bartłomiej Bosek	Lowerbound for Online Chain Partitioning of Upgrowing Interval Posets
	Bartek presents that there is no online algorithm for chain covering problem of upgrowing posets using less than 2w-1 chains to cover a width w poset.
03.11.2004, 27.10.2004, Paweł Walter	Online Bin Packing with two item sizes
	In the well-studied on-line bin packing problem (BPP) we are given a set of items and a sequence of their sizes and are required to pack them into a minimum number of unit-capacity bins. The problem of finding the competitive ratio in the general case is open. In the analysed paper BPP is considered restricted to the case of two distinct item sizes. My talk based on this paper consists of an algorithm solving this particular case at an asymptotic competetive ratio of 4/3 and a proof that 4/3 is also here a valid lower bound.
	references: G.Gutin, T.Jensen, A.Yeo, Optimal on-line bin packing with two item sizes, manuscript (2004)
13.10.2004, Tomek Krawczyk	NP-completeness of posets embedding into boolean lattice
	Let p < q and p,q from N. A bipartitie graph G=(X \cup Y,E) embeds into a lattice of subsets on levels p and q if there exist n from N, injections f: X --> {n \choose p}, g: Y--> {n \choose q} such that there is an edge between x from X and y from Y iff f(x) < g(y). In my talk I proved that the problem of deciding whether a given bipartite graph G=(X \cup Y,E) embeds into lattice of subsets on levels p and q is NP-complete if p>1 and is in P if p=1.
06.10.2004, Piotr Micek	Open Problems from Workshop on On-Line Algorithms 2004

webmaster: www-tcs@tcs.uj.edu.pl