12th workshop of the Center of Modern Computer Science

12. seminář Centra moderní informatiky

The tenth workshop of the Center of Modern Computer Science will take place on Monday December 1, 2017 in the Malá Strana building.

Centrum moderní informatiky zve na dvanáctý seminář. Přednášky juniorů centra se konají v průběhu programu v pátek 1. 12. 2017 v budově MFF UK na Malé Straně.

9:30 (Small Aula, 1st floor)	Andreas Emil Feldmann: Parameterized approximation algorithms for directed Steiner network problems in bidirected graphs
10:00 (Small Aula, 1st floor)	Jiří Fink: Matchings extend to 2-factors in Carthesian graphs
16:00 (Small Aula, 1st floor)	Pavel Hubáček: ARRIVAL: next stop in CLS

Abstracts

Andreas Emil Feldmann: Parameterized approximation algorithms for directed Steiner network problems in bidirected graphs

Given an edge-weighted directed graph G=(V,E) and a set of d terminal pairs (s_1,t_1),...,(s_d,t_d), the objective of the Directed Steiner Network (DSN) problem is to compute the cheapest subgraph N of G such that there is an s_i -> t_i path in N for every i. This problem is notoriously hard, even in the realm of parameterized approximation: for the well-studied parameter k=|{s_i,t_i}|, i.e. the number of terminals, it was recently shown by [Dinur & Manurangsi, 2017] that under Gap-ETH no d^{1/4-o(1)}-approximation is possible for DSN in f(k)*poly(n) time, for any function f(k). The main question we explore is: what approximation factors and runtimes are possible for special cases of DSN when parametrizing by the number of terminals k?

For problems related to DSN it has been fruitful before to analyze the structure of the optimum in order to obtain approximation and FPT algorithms. Therefore, we consider the DSN_K problem, where we need to compute the optimum network contained in some class K of graphs. If K for instance is the class of planar graphs, then this generalizes several well-studied special cases, such as DSN on planar input graphs, but also the Directed Steiner Tree problem on general input graphs. Our main result proves that if additionally the input is bidirected, then a parameterized approximation scheme exists if we aim to compute the planar optimum. We also provide several hardness results that show that our obtained runtime is the best possible for this special case, while at the same time no parameterized approximation scheme exists for any generalization of this special case. We also consider the Strongly Connected Steiner Subgraph (SCSS) problem as another special case, which cannot be captured by DSN_K for any non-trivial class K. We prove that a known parameterized 2-approximation is best possible for SCSS, and that on bidirected input graphs the problem is FPT for parameter k.

Jiří Fink: Matchings extend to 2-factors in Carthesian graphs

Let G' be the Cartesian product of a graph G and a 4-cycle. We prove that for every graph G every matching of G' can be extended to a 2-factor in G'. This statement is a generalization of a conjecture by Vandenbussche and West which asserts that every matching of a hypercube can be extended to a 2-factor.

Pavel Hubáček: ARRIVAL: next stop in CLS

We study the computational complexity of ARRIVAL, a zero-player game on switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. It was shown by Dohrau et al. that the problem of deciding termination of this game is contained in the intersection of NP and coNP. Karthik C. S. recently introduced a search variant of ARRIVAL and showed that it is contained in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of ARRIVAL. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of ARRIVAL is contained in the intersection of UP and coUP. Second, we show that the search variant of ARRIVAL is contained in the complexity class CLS. Our main technical contribution is an efficiently verifiable characterization of the unique witness for termination of the ARRIVAL game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete.