2nd workshop of the Center for Foundations of Modern Computer Science

2. workshop Centra základů moderní informatiky

The second workshop of the Center for Foundations of Modern Computer Science will take place on Monday December 10, 2018, at Šámalova chata at Nová Louka in Jizerské hory. It is a part of HOMONOLO 2018.

16:00	Martin Tancer: Hardness of invariants of knots and links and of embeddability in the 3-space.
16:30	Irena Penev: The class of (P_7,C_4,C_5)-free graphs: decomposition, chi-boundedness, and algorithms
17:00	Andreas E. Feldmann: Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

Abstracts

Martin Tancer: Hardness of invariants of knots and links and of embeddability in the 3-space.

We present a gadget based on properties of the Borromean rings and the Hopf link that allows to prove NP-hardness of computing surprisingly many different invariants of knots and links. A particular instance is hardness of computing the number of Reidemeister moves required to untangle a diagram of an unknot. This is in contrast with the fact that the unknot recognition belongs to both NP and co-NP. Knot theory is also closely related to the 3-manifold topology and therefore also to embeddability of complexes in R^3. A variant of our reduction also allows us to show that recognition of complexes embeddable in R^3 is NP-hard.

The talk is based on joint works with A. de Mesmay, Y. Rieck and E. Sedgwick

Irena Penev: The class of (P_7,C_4,C_5)-free graphs: decomposition, chi-boundedness, and algorithms

As usual, P_n denotes the path on n vertices, and C_n denotes the cycle on n vertices. For a family H of graphs, we say that a graph G is H-free if no induced subgraph of G is isomorphic to any graph in H. We present a decomposition theorem for the class of (P_7,C_4,C_5)-free graphs; in fact, we give a complete structural characterization of (P_7,C_4,C_5)-free graphs that do not admit a clique-cutset. We use this decomposition theorem to show that the class of (P_7,C_4,C_5)-free graphs is chi-bounded by a linear function (more precisely, every (P_7,C_4,C_5)-free graph G satisfies chi(G) ≤ (3/2)omega(G)), and to construct polynomial-time algorithms that solve the optimal coloring, maximum weight clique, and maximum weight stable set problems for this class.

This is joint work with Kathie Cameron, Shenwei Huang, and Vaidy Sivaraman.

Andreas E. Feldmann: Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand Steiner Tree is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results.