4th Annual Scientific Meeting of Computer Science Institute of Charles University and Institute for Theoretical Computer Science (CE-ITI)

The meeting takes place on Friday December 18, 2015. All lectures are in the building of MFF UK in Malá Strana, Malostranské nám. 25.

Program

Morning lectures are in the room S5, 2nd floor
9:30 Adam Přenosil: Graphs and contradictions
10:00 Roman Čada: Dominating even subgraphs in cubic graphs
10:30 coffee break
10:40 Peter Bro Miltersen: Recent results on concurrent reachability games
11:45 lunch at a nearby restaurant
Afternoon lectures are in the room S6, 2nd floor
14:30 Josef Cibulka: Furedi-Hajnal Constants are Typically Subexponential
15:00 Andreas Emil Feldmann: An Exact Characterization of Tractable Demand Patterns for Directed Steiner Network Problems
15:30 Jiří Fink: Approximation algorithms for scheduling a group of heat pumps
16:00 Antonín Kučera: Solving Deductive Games

Abstracts

Adam Přenosil: Graphs and contradictions

The four-valued Belnap-Dunn logic is a well-established non-classical logic which provides one way of formally reasoning with contradictory and incomplete information. However, apart from a few isolated cases, very little is known about its extensions. In this talk, we shall investigate the rich landscape of logics lying between the Belnap-Dunn logic and classical logic. In particular, we shall outline a somewhat surprising connection between these logics and classes of finite graphs with loops and obtain as a corollary that there is a continuum of such logics.

Roman Čada: Dominating even subgraphs in cubic graphs

(This is a joint work with S. Chiba, K. Ozeki and K. Yoshimoto.)

In the talk we present several results on existence of specific even subgraphs in cubic graphs. We mention connections to line graphs or claw free graphs and also to the TSP.

Peter Bro Miltersen: Recent results on concurrent reachability games

Concurrent Reachability Games is a well-known class of zero-sum two-player games played on finite graphs. We survey recent results on such games from the last five years, emphasizing the tool of real algebraic geometry for computationally solving them.

Josef Cibulka: Furedi-Hajnal Constants are Typically Subexponential

(Joint work with Jan Kyncl)

A binary matrix is a matrix with entries from the set {0,1}. We say that a binary matrix A contains a binary matrix S if S can be obtained from A by removal of some rows, some columns, and changing some 1-entries to 0-entries. If A does not contain S, we say that A avoids S. A k-permutation matrix P is a binary k times k matrix with exactly one 1-entry in every row and one 1-entry in every column.

The Furedi-Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix P, there is a constant c_P such that for every natural number n, every n times n binary matrix A with at least c_P n 1-entries contains P.

Fox proved that c_P ≤ 2^(O(k)) for every k-permutation matrix P and that c_P ≥ 2^(Omega*(k^(1/2))) for asymptotically almost all k-permutation matrices. We show that c_P ≤ 2^(O*(k^(2/3)) for asymptotically almost all k-permutation matrices. (The Omega* and O* notation hides a polylogarithmic factor.)

The Stanley-Wilf conjecture says that the number of n-permutation matrices that avoid a fixed k-permutation matrix P is at most (s_P)^n for some constant s_P. The validity of this conjecture follows from the validity of the Furedi-Hajnal conjecture by Klazar's reduction. Extension of the Furedi-Hajnal conjecture to higher-dimensional matrices was found by Klazar and Marcus. We extend the Stanley-Wilf conjecture to higher-dimensional matrices.

Andreas Emil Feldmann: An Exact Characterization of Tractable Demand Patterns for Directed Steiner Network Problems

(This is joint work with Daniel Marx.)

We are interested in the fixed-parameter tractability (FPT) of the Directed Steiner Network (DSN) problem, where we are given a directed edge-weighted graph G with a specified set of terminal vertices R, and a "pattern graph" H, which is a directed (unweighted) graph with vertex set R. The aim is to find the cheapest subgraph N of G that implements all connectivity requirements given by H on the terminals. That is, there is a path in N from s to t if there is an edge st in H. This generalizes the Directed Steiner Tree (DST) problem, where H is always an out-star, and the Strongly Connected Steiner Subgraph (SCSS) problem, where H is always a strongly connected graph. For the parameter k=|R|, it is known that DST is FPT while SCSS is W[1]-hard and thus is unlikely to be FPT. We therefore ask for what classes C of pattern graphs the DSN problem restricted to C is FPT for parameter k. We show that the problem is FPT whenever the class C consists of caterpillar graphs with an additional constant number of edges, and it is W[1]-hard otherwise. Hence we obtain a complete characterization of the complexity of the problem in terms of its class of patterns.

Jiří Fink: Approximation algorithms for scheduling a group of heat pumps

In my talk, I will discuss planning problems for a group of heating systems which supply the hot water demand for domestic use in houses. These systems (e.g. gas or electric boilers, heat pumps or microCHPs) use an external energy source to heat up water and store this hot water for supplying the domestic demands. The latter allows to some extent a decoupling of the heat production from the heat demand. I will focus on the situation where each heating system has its own demand and buffer and the supply of the heating systems is coming from a common source. In practice, the common source may lead to a coupling of the planning for the group of heating systems. The bottleneck to supply the energy may be the capacity of the distribution system (e.g. the electricity networks or the gas network). As this has to be dimensioned for the maximal consumption, it is important to minimize the maximal peak. This planning problem is known to be NP-hard. I will present polynomial-time approximation algorithms for four variants of peak minimization problems and I will determine the worst-case approximation error.

Antonín Kučera: Solving Deductive Games

We propose a general framework for modelling and solving deductive games, where one player selects a secret code and the other player strives to discover this code using a minimal number of allowed experiments that reveal some partial information about the code. The framework is implemented in a software tool Cobra, and its functionality is demonstrated by producing new results about existing deductive games.