View: session overviewtalk overview

09:00 | Improved Approximation Algorithms for the Traveling Tournament Problem PRESENTER: Jingyang Zhao ABSTRACT. The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, minimizing the total distance traveled by all $n$ teams ($n$ is even). TTP-$k$ is the problem with one more constraint that each team can have at most $k$ consecutive home games or away games. The case where $k=3$, TTP-3, is one of the most investigated cases. In this paper, we improve the approximation ratio of TTP-3 from $(1.667+\epsilon)$ to $(1.598+\epsilon)$, for any $\epsilon>0$. Previous schedules were constructed based on a Hamiltonian cycle of the graph. We propose a novel construction based on triangle packing. Then, by combining our triangle packing schedule with the Hamiltonian cycle schedule, we obtain the improved approximation ratio. The idea of our construction can also be extended to $k\geq 4$. We demonstrate that the approximation ratio of TTP-4 can be improved from $(1.750+\epsilon)$ to $(1.700+\epsilon)$ by the same method. As an additional product, we also improve the approximation ratio of LDTTP-3 (TTP-3 where all teams are allocated on a straight line) from $4/3$ to $(6/5+\epsilon)$. |

09:25 | Constant-factor approximation algorithm for binary search in trees with monotonic query times ABSTRACT. We consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns feedback that either v is the target or the edge incident to v is given that is on the path towards the target. The goal of the algorithm is to find a strategy that minimizes the worst-case total cost. We propose a constant-factor approximation algorithm for trees with a monotonic cost function. Such function is defined as follows: there exists a vertex r such that for any two vertices u, v on any path connecting r with a leaf it holds that if u is closer to r than v, then ω(u) ≥ ω(v). The best-known approximation algorithm for general weight functions has the ratio of O(√log n) [Dereniowski et al. ICALP 2017] and it remains a challenging open question whether the constant-factor approximation is achievable in such a case. This gives our first motivation towards considering monotonic cost functions and the second one lies in the potential applications. |

09:50 | Rabbits approximate, cows compute exactly! ABSTRACT. Valiant, in his seminal paper in 1979, showed an efficient simulation of algebraic formulas by determinants, showing that $\mathsf{VF}$, the class of polynomial families computable by polynomial-sized algebraic formulas, is contained in $\mathsf{VDet}$, the class of polynomial families computable by polynomial-sized determinants. Whether this containment is strict has been a long-standing open problem. We show that algebraic formulas can in fact be efficiently simulated by the determinant of tetradiagonal matrices, transforming the open problem into a problem about determinant of general matrices versus determinant of tetradiagonal matrices with just three non-zero diagonals. This is also optimal in a sense that we cannot hope to get the same result for matrices with only two non-zero diagonals or even tridiagonal matrices, thanks to Allender and Wang (Computational Complexity'16) which showed that the determinant of tridiagonal matrices cannot even compute simple polynomials like $x_1x_2 + x_3x_4 + \cdots + x_{15}x_{16}$. Our proof involves a structural refinement of the simulation of algebraic formulas by width-3 algebraic branching programs by Ben-Or and Cleve (SIAM Journal of Computing'92). The tetradiagonal matrices we obtain in our proof are also structurally very similar to the tridiagonal matrices of Bringmann, Ikenmeyer and Zuiddam (JACM'18) which showed that, if we allow approximations in the sense of geometric complexity theory, algebraic formulas can be efficiently simulated by the determinant of tridiagonal matrices of a very special form, namely the continuant polynomial. The continuant polynomial family is closely related to the Fibonacci sequence, which was used to model the breeding of rabbits. The determinants of our tetradiagonal matrices, in comparison, is closely related to Narayana's cows sequences, which was originally used to model the breeding of cows. Our result shows that the need for approximation can be eliminated by using Narayana's cows polynomials instead of continuant polynomials, or equivalently, shifting one of the outer diagonals of a tridiagonal matrix one place away from the center. Conversely, we observe that the determinant (or, permanent) of band matrices can be computed by polynomial-sized algebraic formulas when the bandwidth is bounded by a constant, showing that the determinant (or, permanent) of bandwidth $k$ matrices for all constants $k \geq 2$ yield $\mathsf{VF}$-complete polynomial families. In particular, this implies that the determinant of tetradiagonal matrices in general and Narayana's cows polynomials in particular yield complete polynomial families for the class $\mathsf{VF}$. |

10:50 | On vanishing sums of roots of unity in polynomial calculus and sum-of-squares PRESENTER: Ilario Bonacina ABSTRACT. Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size. |

11:15 | Complete ZX-calculi for the stabiliser fragment in odd prime dimensions ABSTRACT. We introduce a family of ZX-calculi which axiomatise the stabiliser fragment of quantum theory in odd prime dimensions. These calculi recover many of the nice features of the qubit ZX-calculus which were lost in previous proposals for higher-dimensional systems. We then prove that these calculi are complete, i.e. provide a set of rewrite rules which can be used to prove any equality of stabiliser quantum operations. Finally, we relate them to the graphical language for affine Lagrangian relations, which also axiomatises the stabiliser fragment. Adding a discard construction, we obtain a calculus complete for mixed state stabiliser quantum mechanics in odd prime dimensions, and this furthermore gives a complete axiomatisation for the related diagrammatic language for affine co-isotropic relations. |

11:40 | Countdown mu-calculus ABSTRACT. We introduce the countdown mu-calculus, an extension of the modal mu-calculus with ordinal approximations of fixpoint operators. In addition to properties definable in the classical calculus, it can express (un)boundedness properties such as the existence of arbitrarily long sequences of specific actions. The standard correspondence with parity games and automata extends to suitably defined countdown games and automata. However, unlike in the classical setting, the scalar fragment is provably weaker than the full vectorial calculus and corresponds to automata satisfying a simple syntactic condition. We establish some facts, in particular decidability of the model checking problem and strictness of the hierarchy induced by the maximal allowed nesting of our new operators. |

16:30 | Dispersing Obnoxious Facilities on Graphs by Rounding Distances ABSTRACT. We continue the study of $\delta$-dispersion, a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that every two facilities have distance at least $\delta$ from each other. Our main technical contribution is an efficient procedure to `round-up' distance $\delta$. It transforms a $\delta$-dispersed set $S$ into a set $S'$ of same size such that $S'$ is $\delta'$-dispersed with a slightly larger rational distance $\delta'$ where the numerator is upper bounded by the longest (not-induced) path in the input graph. Based on this rounding procedure and connections to the distance-d independent set problem we can derive a number of algorithmic results. When parameterized by treewidth, the problem is in XP. When parameterized by treedepth the problem is FPT and has a matching lower bound on its time complexity under ETH. Moreover, we can also settle the parameterized complexity with the solution size as parameter using our rounding technique: $\delta$-\dispersion is FPT for every $\delta \leq 2$ and W[1]-hard for every $\delta > 2$. Further, we show that $\delta$-dispersion is NP-complete for every fixed irrational distance $\delta$, which was left open in previous work. |

16:55 | Graph Realization of Distance Sets ABSTRACT. The Distance Realization problem is defined as follows. Given an $n \times n$ matrix $D$ of nonnegative integers, interpreted as inter-vertex distances, find an $n$-vertex weighted or unweighted graph $G$ realizing $D$, i.e., whose inter-vertex distances satisfy $\dist_G(i,j)=D_{i,j}$ for every $1\le i<j\le n$, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e.g., trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix $D$ may contain a \emph{range} of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most $k$ values yields the problem $k$-Range Distance Realization (or $k$-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry $D_{i,j}$ of the matrix may contain an arbitrary set of acceptable values for the distance between $i$ and $j$. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most $k$ values as $k$-Set Distance Realization (or $k$-Set-DR). We first show that 2-Rnage-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. We then explore Set-DR where the realization is restricted to the families of stars, paths, or cycles. For the weighted case, our positive results are that for each of these families there exists a polynomial time algorithm for 2-Set-DR. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths and cycles. For the unweighted case, our results are the same, except for the case of unweighted stars, for which $k$-Set-DR is polynomially solvable for any $k$. |

17:20 | The complexity of computing optimum labelings for temporal connectivity PRESENTER: Nina Klobas ABSTRACT. A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex $u$ to every other vertex $v$. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph $G$, what is the smallest number $|\lambda|$ of time-labels that we need to add to the edges of $G$ such that the resulting temporal graph $(G,\lambda)$ is temporally connected? As it turns out, this basic problem, called MINIMUM LABELING (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem MINIMUM AGED LABELING (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e. maximum label) of the obtained temporal graph $(G,\lambda)$. Second we consider the problem MINIMUM STEINER LABELING (MSL), where the aim is now to have a temporal path between any pair of ``important'' vertices which lie in a subset $R\subseteq V$, which we call the terminals. This relaxed problem resembles the problem STEINER TREE in static (i.e. non-temporal) graphs. However, due to the requirement of strictly increasing labels in a temporal path, STEINER TREE is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely MINIMUM AGED STEINER LABELING (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number $|R|$ of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL remains NP-hard, it is in FPT with respect to the number $|R|$ of terminals. That is, adding the age restriction, makes the above problems strictly harder (unless P=NP or W[1]=FPT). |