Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. ucz.

Information

Home page

List of talks

• July 6, 2017, 12:15 p.m.
  Brynmor Chapman (Massachusetts Institute of Technology)
  A Refutation of the Gotsman-Linial Conjecture
  A degree-$d$ polynomial threshold function is a function that can be written as the sign of a degree-$d$ polynomial on the Boolean hypercube.  Bounds on the sensitivity of polynomial threshold functions to small changes in …

  ---

• June 8, 2017, 12:15 p.m.
  Marek Adamczyk (University of Warsaw)
  When the Optimum is also Blind: a New Perspective on Universal Optimization
  Consider the following variant of the set cover problem. We are given a universe $U={1,2,...,n}$ and a collection of subsets C={S_1,...,S_m} where each S_i is a subset of U. For every element u of U …

  ---

• May 11, 2017, 12:15 p.m.
  Till Miltzow (Universit ́e libre de Bruxelles)
  The Art Gallery Problem is $\exists \mathbb{R}$-complete
  The \emph{art gallery problem} is a classical problem in computational geometry, introduced in 1973 by Viktor Klee. Given a simple polygon \poly and an integer $k$, the goal is to decide if there exists a …

  ---

• April 20, 2017, 12:15 p.m.
  Marcin Wrochna (University of Warsaw)
  A topological approach related to Hedetniemi's conjecture
  Hedetniemi's 50 years old conjecture states that the chromatic number of the tensor product of graphs G,H is the minimum of the chromatic numbers of G and H. The conjecture has many interesting connections with …

  ---

• March 23, 2017, 12:15 p.m.
  Paweł Rzążewski (Politechnika Warszawska)
  Fine-grained complexity of coloring disks, balls, and segments.
  On planar graphs, many classic algorithmic problems enjoy a certain ``square root phenomenon'' and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian …

  ---

• March 16, 2017, 12:15 p.m.
  Andreas Emil Feldmann (Charles University)
  The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
  Given a directed graph G and a list (s1 , t1 ), . . . , (sk , tk ) of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of G …

  ---

• March 9, 2017, 12:15 p.m.
  Konstanty Junosza-Szaniawski (Politechnika Warszawska)
  2,1)-labeling of unit disk intersection graphs (Online coloring and L)
  We give a family of online algorithms for the classical coloring and the L(2,1)-labeling problems of unit disk intersection graphs. In the L(2,1)-labeling we ask for an assignment of non-negative integers to the vertices of …

  ---

• Feb. 9, 2017, 12:15 p.m.
  Marthe Bonamy (Université de Bordeaux)
  Using region decomposition techniques for coloring problems
  We consider the problem of coloring the square of a planar graph that has no small cycle. We prove a conjecture of Dvorak, Kral, Nejedly, and Skrekovski that planar graphs of girth at least five …

  ---

• Jan. 12, 2017, 12:15 p.m.
  O-joung Kwon (Technische Universitat Berlin)
  Parameterized complexity of Distance-Hereditary Vertex Deletion
  A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both vertices is the same as their distance in the original graph. Distance-hereditary graphs are exactly the …

  ---

• Dec. 15, 2016, 12:15 p.m.
  Marcin Wrochna (University of Warsaw)
  tw)*n time (Algorithms for graphs and matrices in poly)
  Abstract: Knowing how small treewidth can be exploited algorithmically in NP-hard problems, we ask about speeding up classical polynomial-time algorithms to (quasi-)linear in the graph size, while keeping the dependency on treewidth polynomial. We provide …

  ---

• Dec. 1, 2016, 12:15 p.m.
  Bartosz Walczak (Uniwersytet Jagielloński)
  Coloring graphs with geometric representations and related problems
  Colorings of graphs represented by geometric objects have been studied since the 1960s for both theoretical and practical reasons. In particular, geometric representations lead to natural examples of classes of graphs that are χ-bounded (near-perfect), …

  ---

• Nov. 24, 2016, 12:15 p.m.
  Andrzej Grzesik
  Minimum number of edges that occur in odd cycles
  For any fixed k>1 every graph without a cycle on 2k+1 vertices has at most n^2/4 edges. In 1992, Erdos, Faudree and Rousseau conjectured that if a graph has at least n^2/4 + 1 edges, …

  ---

• Nov. 17, 2016, 12:15 p.m.
  Erik Jan van Leeuwen
  Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
  We consider the recognition problem for two graph classes that generalize split and unipolar graphs, respectively. First, we consider the recognizability of graphs that admit a monopolar partition: a partition of the vertex set into …

  ---

• Nov. 3, 2016, 12:15 p.m.
  Łukasz Kowalik
  On the Fine-Grained Complexity of Rainbow Coloring
  The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in k colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all …

  ---

• Oct. 20, 2016, 12:15 p.m.
  Daniel Marx
  The Optimality Program in Parameterized Algorithms
  Parameterized complexity analyzes the computational complexity of NP-hard combinatorial problems in finer detail than classical complexity: instead of expressing the running time as a univariate function of the size $n$ of the input, one or …

  ---