FIT 2018

A tree with $n$ vertices has at most $95^{n/13}$ minimal dominating sets. The corresponding growth constant $95^{1/13}\approx 1.4194908$ is best possible.

I will show how these results are obtained in a semi-automatic way with computer help, starting from the dynamic-programming recursion for computing the number of minimal dominating sets of a given tree. This recursion defines a bilinear operation on sixtuples, and the growth constant arises as a kind of "dominant eigenvalue" of this operation.

We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between reporting successive solutions. It is open whether the delay can be reduced to a constant delay, for an appropriate modification of the problem statement.

In the talk I will discuss two related notions with regards to graph compression.

• Given a graph (directed or undirected, weighted or unweighted) $G$ with $n$ vertices, and a set $P$ of $p$ pairs of vertices, a distance sparsifier is an edge-minimal subgraph of $G$ that maintains the same lengths of shortest paths between the pairs in $P$. A natural question is to obtain as small as possible size of a distance sparsifier, expressed as a function of $n$ and $p$.
• Given an edge-weighted graph $G$ with a set $Q$ of $k$ terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between any partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph $G$ being either an arbitrary graph or coming from a specific graph class.

In many special cases, the known upper and lower bounds for the above concepts are surprising far from each other. In the talk, I will survey these areas, with emphasize on open problems. Furthermore, I will present our recent result obtained in a joint work with Nikolai Karpov and Anna Zych-Pawlewicz, namely an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with $k$ terminals that require $2^{k−2}$ edges in any mimicking network.

Feedback Vertex Set is a classic combinatorial optimization problem that asks for a minimum set of vertices in a given graph whose deletion makes the graph acyclic. From the point of view of parameterized algorithms and fixed-parameter tractability, Feedback Vertex Set is one of the landmark problems: a long line of study resulted in multiple algorithmic approaches and deep understanding of the combinatorics of the problem. Because of its central role in parameterized complexity, the first edition of the Parameterized Algorithms and Computational Experiments Challenge (PACE) in 2016 featured Feedback Vertex Set as the problem of choice in one of its tracks.

The results of PACE 2016 on one hand showed large discrepancy between performance of different classic approaches to the problem, and on the other hand indicated a new approach based on half-integral relaxations of the problem as probably the most efficient approach to the problem. In this talk we provide an exhaustive experimental evaluation of fixed-parameter and branching algorithms for Feedback Vertex Set.

The notion of treewidth, introduced by Robertson and Seymour in their seminal Graph Minors series, turned out to have tremendous impact on graph algorithmics. Many hard computational problems on graphs turn out to be efficiently solvable in graphs of bounded treewidth: graphs that can be swept with separators of bounded size. These efficient algorithms usually follow the dynamic programming paradigm.

In the recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth. One of the most surprising directions is the development of algorithms for connectivity problems that have only single-exponential dependency (i.e., $2^{O(t)}$) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., $2^{O(t\log t)}$) stemming from more naive approaches. In this work, we perform a thorough experimental evaluation of these approaches in the context of one of the most classic connectivity problem, namely Hamiltonian Cycle.

We study the problem of finding a minimum weight connected subgraph spanning at least $k$ vertices on planar, node-weighted graphs. We give a $(4+\varepsilon)$-approximation algorithm for this problem. We achieve this by utilizing the recent LMP primal-dual $3$-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al. (SWAT’16) and adopting an approach by Chudak et al. (Math. Prog. ’04) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. ’06).

More generally, our approach readily gives a $(4/3\cdot r+\varepsilon)$-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an $r$-approximation. We argue that this can be interpreted as a generalization of an analogous result by Könemann et al. (Algorithmica ’11) for partial cover problems. Together with a lower bound construction by Mestre (STACS’08) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a non-black-box fashion could not beat the factor $4/3\cdot r$ when the tree merging step relies only on the solutions output by the LMP algorithm.

We give faster and simpler approximation algorithms for the $(1,2)$-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either $1$ or $2$.

Our main results are two approximation algorithms for $(1,2)$-TSP, one with approximation factor $8/7$ and run time $O(n^3)$ and the other having an approximation guarantee of $7/6$ and run time $O(n^{2.5})$. The $8/7$-approximation matches the best known approximation factor for $(1,2)$-TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of $O(n^9)$. Thus, ours is the first improvement for the $(1,2)$-TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "half-edges". The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an $8/7$-approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best $8/7$-approximation.

The $7/6$-approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimum-cost triangle-free cycle cover.

The subject of this paper is the time complexity of approximating Knapsack, Subset Sum, Partition, and some other related problems. The main result is an $O((n+1/\varepsilon)^{5/3})$ time randomized FPTAS for Partition, which is derived from a certain relaxed form of a randomized FPTAS for Subset Sum. To the best of our knowledge, this is the first NP-hard problem that has been shown to admit a subquadratic time approximation scheme, i.e., one with time complexity of $O((n+1/\varepsilon)^{2-\delta})$ for some $\delta>0$. To put these developments in context, note that a quadratic FPTAS for Partition has been known for 40 years.

Our main contribution lies in designing a mechanism that reduces an instance of Subset Sum to several simpler instances, each with some special structure, and keeps track of interactions between them. This allows us to combine techniques from approximation algorithms, pseudo-polynomial algorithms, and additive combinatorics.

We also prove several related results. Notably, we improve approximation schemes for 3SUM, $(\min,+)$-convolution, and Tree Sparsity. Finally, we argue why breaking the quadratic barrier for approximate Knapsack is unlikely by giving an $\Omega((n+1/\varepsilon)^{2-o(1)})$ conditional lower bound.

Production and distribution are fundamental operational functions in supply chains. The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution to customers afterwards. The goal is to minimize the total time from release to distribution plus total distribution cost to the customers. We design the first poly-logarithmic competitive algorithm for the problem, improving upon previous algorithms with linear competitive ratios. Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines (where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.

We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) introduced by Emek et al. (STOC 2016). In this problem, an even number of requests appear in a metric space at different times and the goal of an online algorithm is to match them in pairs. In contrast to traditional online matching problems, in MPMD all requests appear online and an algorithm can match any pair of requests, but such decision may be delayed (e.g., to find a better match). The cost is the sum of matching distances and the introduced delays. We present the first deterministic solutions for this problem.

Hide and seek games, introduced by John von Neumann, are among the oldest classes of games studied in game theory. These games are closely related to security games, studied extensively in artificial intelligence, and are an example of conflicts with multiple battlefields with discrete resources. We will present analytical characterization of equilibria of these games and show how it can be used to improve existing algorithms for finding equilibria in such games.

To choose a suitable multi-winner rule, i.e., a voting rule for selecting a subset of $k$ alternatives based on a collection of preferences, is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an "optimal" subset. In this paper, we offer a new perspective to measure the quality of such subsets and – consequently – multi-winner rules. We provide a quantitative analysis using methods from the theory of approximation algorithms and estimate how well multi-winner rules approximate two extreme objectives: diversity as captured by the (Approval) Chamberlin–Courant rule and individual excellence as captured by Multi-winner Approval Voting. With both theoretical and experimental methods we classify multi-winner rules in terms of their quantitative alignment with these two opposing objectives.

A fan is a graph obtained from a path by adding an extra vertex adjacent to all vertices on the path. We give a qualitative structure theorem for graphs excluding a fan as a minor. This is inspired by a recent result by Ding that gives an approximate description of graphs excluding $K_{2,n}$ as a minor. Next, we use both characterizations to show that the dimension of a poset is bounded in terms of the size of a largest $K_{2,n}$ or a fan (graph) which is a minor of the cover graph. This is a step towards characterization of minor-closed graph classes such that posets with cover graphs from such a class have bounded dimension.

We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called $k$-LCIS: Given $k$ integer sequences $X_1,\ldots,X_k$ of length at most $n$, the task is to determine the length of the longest common subsequence of $X_1,\ldots,X_k$ that is also strictly increasing. Especially for the case of $k=2$ (called LCIS for short), several algorithms have been proposed that require quadratic time in the worst case.

Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight lower bound, specifically, that no algorithm solves LCIS in (strongly) subquadratic time. Interestingly, the proof makes no use of normalization tricks common to hardness proofs for similar problems such as LCS. We further strengthen this lower bound (1) to rule out $O((nL)^{1-\varepsilon})$ time algorithms for LCIS, where $L$ denotes the solution size, (2) to rule out $O(n^{k-\varepsilon})$ time algorithms for $k$-LCIS, and (3) to follow already from weaker variants of SETH. We obtain the same conditional lower bounds for the related Longest Common Weakly Increasing Subsequence problem.

This is joint work with Lech Duraj and Marvin Künnemann, presented at IPEC 2017.

Locally consistent parsing is a common name for a family of schemes which build a parse tree over the input text so that any two equal fragments are parsed in essentially the same way. Several constructions, including the original one by Sahinalp and Vishkin and the much more recent recompression by Artur Jeż, appear in state-of-the-art solutions to many problems of text algorithms: in compressed pattern matching, dynamic indexing, word equations, and more. At SODA 2015, with J. Radoszewski, W. Rytter and T. Waleń, we introduced a related notion of locally consistent representative assignment in order to design efficient data structures for internal queries – questions concerning fragments of a static text. For example, the periods of any fragment of a length-$n$ text can be retrieved in $O(\log n)$ time using our linear-size data structure.

In the talk, I will report a new discovery concerning the fundamental LCE queries, which ask for the longest common prefix of any two fragments. For a text of length $n$, the textbook solutions, based on the suffix tree or the suffix array, take $O(n\log n)$ bits even if the alphabet size $\sigma$ is constant. Local consistency lets us achieve for the first time the optimal space of $O(n\log\sigma)$ bits while preserving $O(1)$ query time. Moreover, our data structure can be constructed deterministically in $O(n\log\sigma/\log n)$ time provided that $\Theta(\log_\sigma n)$ characters are packed in each machine word representing the input text.

We propose a new, worst-case cubic-time, generalized parsing algorithm for all context-free languages, based on computing the relations between configurations and transitions in a recursive transition network. The algorithm represents such relations using abstract data types, and for their specific (non-canonical) implementations behaves analogously to generalized LL, Left-Corner, or LR. It features a clean mathematical formulation, and can easily be implemented using only immutable data structures.

Introducing static typing to dynamic languages (such as Python or JavaScript) is an active research field which can produce better IDEs and improve Just-In-Time compilers for these languages. However, construction of a type system for mainstream dynamic languages that feature runtime object modification requires solution to multiple undecidable subproblems. The main reason is that even computing the validity of usage of a dot operator (object.property) requires information whether the property was assigned to the object during the runtime (object.property := value), which in turn requires full alias analysis of the program (which is undecidable).

My approach to this problem is introduction of strong invariants to a type system of such a language. These strong invariants are used to check at runtime whether some basic properties are satisfied (e.g., a property of an object is not modified or removed throughout the evaluation of an expression), and give the type system additional information to work with. I will describe the ideas behind this approach on a small dynamic language that models most essential features of the Python language.

Staging in programming languages is a mechanism that allows for partial execution of a program in multiple phases. Each phase produces a new code that is specialized with respect to some parameters. Typical phases are compile-time and run-time evaluation, but there can be more.

In this talk, we present our approach to staging. Formally, it is a small extension to lambda calculus. Practically, it provides a first-class entity that can be used to control the order of execution and trigger multiple stages at the programmer's will. The staging can be parametrized, and the same code can be reused between stages or be specialized in a different way.

We show a few practical examples, as well as how dynamic staging fits in our bigger project: ManyDSL.

For a given set of queries (which are expressions in some query language) $\mathcal{Q}=\{Q_1,Q_2,\ldots,Q_k\}$ and for another query $Q_0$ we say that $\mathcal{Q}$ determines $Q_0$ if – informally speaking – for every database $\mathbb{D}$, the information contained in the views $\mathcal{Q}(\mathbb{D})$ is sufficient to compute $Q_0(\mathbb{D})$.

Query Determinacy Problem is the problem of deciding, for given $\mathcal{Q}$ and $Q_0$, whether $\mathcal{Q}$ determines $Q_0$. Many versions of this problem, for different query languages, were studied in database theory. In this paper we solve a problem stated in [CGLV02] and show that Query Determinacy Problem is undecidable for the Regular Path Queries – the paradigmatic query language of graph databases.

Decidability of many standard decision problems for Petri nets becomes an open problem once we extend the model with data. If we restrict only to homogeneous data domains, according to the WQO Dichotomy Conjecture there exists a simple criterion for decidability. I will introduce the model of Petri nets with data, state the conjecture and say what is currently known about it.

We survey algorithmic and complexity results on Constraint Satisfaction Problems (CSPs) and related computational problems. In particular, we discuss various dichotomy results and characterisations of power of algorithms.

Unary negation fragment of first-order logic, UNFO, has been recently introduced by ten Cate and Segoufin. It turns out to have good algorithmic and model-theoretic properties, including decidability of the satisfiability problem and the finite model property. At the same time, its expressive power is quite attractive. In particular it embeds propositional (multi)-modal logic and unions of conjunctive queries.

In this talk we consider an extension of UNFO in which arbitrarily many binary symbols may be required to be interpreted either as equivalence relations or as arbitrary transitive relations. We show that in both cases the satisfiability and the finite satisfiability problem remain decidable and that the variant with equivalences retains the finite model property.

Satisfiability of Boolean circuits is NP-complete in general but becomes polynomial time when restricted for example either to monotone gates or linear gates. We go outside Boolean realm and consider circuits built of any fixed set of gates on an arbitrary large finite domain. From the complexity point of view this is connected with solving equations over finite algebras. This in turn is one of the oldest and well-known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. The last problem has been shown to be undecidable, however in finite realms such problems are obviously decidable in nondeterministic polynomial time.

A project of characterizing finite algebras $\mathbb{A}$ with polynomial time algorithms deciding satisfiability of circuits over $\mathbb{A}$ has been undertaken in [P. M. Idziak and J. Krzaczkowski, Satisfiability in multi-valued circuits, LICS 2018]. Unfortunately that paper leaves a gap for nilpotent but not supernilpotent algebras. In my talk I will discuss a class of nilpotent algebras, for which the problem is tractable in polynomial time. I will also show how those results could be applied to analyze 3-SAT formulas.

We extend the modal $\mu$-calculus to sets with atoms and we study its basic properties. Model checking is decidable on orbit-finite structures, but satisfiability becomes undecidable. We also show expressive limitations of atom-enriched $\mu$-calculi, and explain how their expressive power depends on the structure of atoms used, and on the choice between basic or vectorial syntax.

Algorithms that decide satisfiability problem for extensions of the two variable logic with counting quantifiers (C2 for short) can be quite involved. One not only has to take care to construct a model of C2 formula, but also to impose appropriate interpretation of distinguished symbols (mother-daughter relations in forests, successors of linear orders, equivalence relations etc.). Resulting proofs become technically challenging and the essence of reasoning is lost in technical details. To cope with this problem we introduce a black-box technique, a method that reduces satisfiability problem for an extension of C2 to a weaker extension of C2, or even to C2 itself. With this method we show that the finite satisfiability for C2 with two independent unranked unordered forests is NEXPTIME-complete, and that the (general) satisfiability problem for C2 with a single forest is also NEXPTIME-complete.

Jumping automata caught a lot of attention in the past few years and were considered in numerous papers [4, 1]. The head of a jumping automaton does not read the input word from left to right like in a classical finite automaton, but jumps nondeterministically to arbitrary positions in the word to read and delete parts of it.

Recently, two-dimensional row jumping finite automata were introduced as an interesting computational model for accepting two-dimensional languages [2]. These automata are nondeterministic. They guess an order in which rows of the input array are read and they jump to the next row only after reading all symbols in the previous row. In each row, they use a jumping mode to read and erase segments of the row.

We present our results regarding the membership problem for these automata [3]. We show that each row jumping finite automaton can be simulated by a nondeterministic Turing machine with space bounded by the logarithm. This means that the fixed membership problems for such automata are in P. On the other hand, we show that the uniform membership problem is NP-complete.

References:

1. Henning Fernau, Meenakshi Paramasivan, Markus L. Schmid, and Vojtěch Vorel. Characterization and complexity results on jumping finite automata. Theoretical Computer Science, 679:31–52, 2017.
2. S. James Immanuel and D. G. Thomas. Two-dimensional jumping finite automata. Mathematics for Applications, 5:105–122, 2016.
3. Alexander Meduna and Petr Zemek. Jumping finite automata. International Journal of Foundations of Computer Science, 23(7):1555–1578, 2012.
4. Grzegorz Madejski and Andrzej Szepietowski. Membership problem for two-dimensional jumping finite automata. In Rudolf Freund, František Mráz, and Daniel Průša, editors, NCMA 2017: Ninth Workshop on Non-Classical Models of Automata and Applications – Short Papers, pages 34–40, 2017.

I will discuss the recent results on weighted automata (where weights are aggregated using functions like sum or average) under probabilistic semantics, including computing the expected value and the cumulative distribution of a given automaton w.r.t. word distribution given by a Markov chain. These results can be applied to approximately determinise weighted automata and shed some light on the weighted automata learning problem.

We propose an axiomatization of PageRank. Specifically, we introduce five simple axioms – Foreseeability, Outgoing Homogeneity, Monotonicity, Merging, and Dummy Node – and show that PageRank is the only centrality measure that satisfies all of them. Our axioms give new conceptual and theoretical underpinnings of PageRank and show how it differs from other centralities.

We study the problem of extending the classic centrality measures to weighted graphs. Unfortunately, in the existing extensions, paths in the graph are evaluated solely based on their weights, which is a restrictive and undesirable assumption for a variety of settings. Given this, we define a notion of the path evaluation function that assesses a path between two nodes by looking not only on the sum of edge weights, but also on the number of intermediaries. Using an axiomatic approach, we propose three classes of path evaluation functions. Building upon this analysis, we present the first systematic study how classic centrality measures can be extended to weighted graphs while taking into account an arbitrary path evaluation function. As an application, we use the newly-defined measures to identify the most well-linked districts in a sample public transport network.

I will present how centrality measures can be used for the advanced analysis of public transport networks. In particular, it allows to answer questions such as "how to identify the most well-linked district in Kraków" or "which bus stop have the best direct connections to other parts of the city".

We present a distributed randomized algorithm finding Minimum Spanning Tree (MST) of a given graph in $O(1)$ rounds, with high probability, in the Congested Clique model. The input graph in the Congested Clique model is a graph of $n$ nodes, where each node initially knows only its incident edges. The communication graph is a clique with limited edge bandwidth: each two nodes (not necessarily neighbours in the input graph) can exchange $O(\log n)$ bits.

As in previous works, the key part of the MST algorithm is an efficient Connected Components (CC) algorithm. However, unlike the former approaches, we do not aim at simulating the standard Borůvka algorithm, at least at initial stages of the CC algorithm. Instead, we develop a new technique which combines partitions of sample sparse subgraphs of the input graph in order to accelerate the process of uncovering connected components of the original input graph. More specifically, we develop a sparsification technique which reduces an initial CC problem in $O(1)$ rounds to its two restricted instances. The former instance has a graph with maximal degree $O(\log\log n)$ as the input – here our sample-combining technique helps. In the latter instance, a partition of the input graph into $O(n/\log\log n)$ connected components is known. This gives an opportunity to apply previous algorithms to determine connected components in $O(1)$ rounds.

Our result improves over previous $O(\log^* n)$ algorithm of Ghaffari et al. [PODC 2016], $O(\log\log\log n)$ algorithm of Hegeman et al. [PODC 2015] and the $O(\log\log n)$ algorithm of Lotker et al. [SPAA 2003; SICOMP 2005]. It also determines $\Theta(1)$ round complexity in the congested clique for MST, as well as other graph problems, including bipartiteness, cut verification, $s$–$t$ connectivity, cycle containment and $O(\log\Delta)$ round complexity of the maximal independent set (MIS).

We consider deterministic distributed communication in wireless ad hoc networks of identical devices in the SINR model without predefined infrastructure. Most algorithmic results in this model rely on various additional features or capabilities, e.g., randomization, access to geographic coordinates, power control, or carrier sensing. We develop a deterministic clustering algorithm, which splits the nodes of the network into groups such that each group is contained in an area of fixed diameter, and there are $O(1)$ groups in any area of constant diameter. Then, we use the clustering algorithm to accomplish broadcast and local broadcast in the network. Our solution relies on a new type of combinatorial structures, which might be of independent interest.

This work was done in collaboration with Leszek Gąsieniec from the University of Liverpool.

The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this paper the emphasis is on the space complexity in fast leader election via population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions from the population of $n$ agents.

The main result of this paper is a new fast and space optimal leader election protocol. The new protocol operates in parallel time $O(\log^2 n)$ equivalent to $O(n\log^2 n)$ sequential pairwise interactions, in which each agent utilises $O(\log\log n)$ states. This double logarithmic space utilisation matches asymptotically the lower bound $\frac{1}{2}\log\log n$ on the number of states utilised by agents in any leader election algorithm with the running time $o(n/\operatorname{polylog}n)$, see [AA+17].