During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al. (in: PODC 2003, pp 347-351, 2003. 10.1145/872035.872088), where agents aim at being as central as possible in the created network. We look at two variants of network creation governed by social distancing. Firstly, a variant without connection restrictions, where we characterize optimal and equilibrium networks, and derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant allows connection restrictions. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that under social distancing the agents' selfishness has a strong impact on the quality of the equilibria.

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton  with amortized update time  per input symbol.

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256-279, 2014), DNF sparsification Gopalan et al. (Comput. Complex. 22:275-310 2013), randomness extractors Li et al. (In: APPROX-RANDOM, LIPIcs 116:51:1-13, 2018), and recent advances on the Erdős-Rado sunflower conjecture Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) Lovett et al. (From dnf compression to sunflower theorems via regularity, 2019) Rao (Discrete Anal. 8,2020). The recent breakthrough of Alweiss, Lovett, Wu and Zhang Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) gives an improved bound on the maximum size of a -set system that excludes a robust sunflower. In this paper, we use this result to obtain an lower bound on the monotone circuit size of an explicit -variate monotone function, improving the previous best known due to Andreev (Algebra and Logic, 26:1-18, 1987) and Harnik and Raz (In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000). We also show an lower bound on the monotone circuit size of a related polynomial via a very simple proof. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an lower bound on the monotone circuit size of the CLIQUE function for all , strengthening the bound of Alon and Boppana (Combinatorica, 7:1-22, 1987).

A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines and , one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given -vertex graph, whether we can remove at most vertices to obtain a bipartite permutation graph. This problem is -complete by the classical result of Lewis and Yannakakis [20]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time , and also give a polynomial-time 9-approximation algorithm.

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) repaving road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c), (d) are restrictions to different graph classes. We show that (a) does not admit polynomial-time algorithms (assuming ), even for relaxed variants of the problem (assuming ). For (b), (c), (d), we present polynomial-time algorithms to solve the respective problems. We also generalize the problem to when at most (for a fixed integer ) contiguous vertices on a shortest path can be changed at a time.

A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of . This paper considers computing cut sparsifiers of weighted graphs of size . Our algorithm computes such a sparsifier in time , both for graphs with polynomially bounded and unbounded integer weights, where is the functional inverse of Ackermann's function. This improves upon the state of the art by Benczúr and Karger (SICOMP, 2015), which takes time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP, 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki forest packing. MSF packings have previously been used by Abraham et al. (FOCS, 2016) in the dynamic setting, and are defined as follows: an -partial MSF packing of is a set , where is a maximum spanning forest in . Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

For an integer , a -recursive sequence is defined by recurrence relations on subsequences of indices modulo some powers of . In this article, -recursive sequences are studied and the asymptotic behavior of their summatory functions is analyzed. It is shown that every -recursive sequence is -regular in the sense of Allouche and Shallit and that a -linear representation of the sequence can be computed easily by using the coefficients from the recurrence relations. Detailed asymptotic results for -recursive sequences are then obtained based on a general result on the asymptotic analysis of -regular sequences. Three particular sequences are studied in detail: We discuss the asymptotic behavior of the summatory functions ofStern's diatomic sequence,the number of non-zero elements in some generalized Pascal's triangle andthe number of unbordered factors in the Thue-Morse sequence. For the first two sequences, our analysis even leads to precise formulæ without error terms.

In this paper, we consider a general notion of convolution. Let be a finite domain and let be the set of -length vectors (tuples) of . Let be a function and let be a coordinate-wise application of . The -Convolution of two functions is for every . This problem generalizes many fundamental convolutions such as Subset Convolution, XOR Product, Covering Product or Packing Product, etc. For arbitrary function and domain we can compute -Convolution via brute-force enumeration in time. Our main result is an improvement over this naive algorithm. We show that -Convolution can be computed exactly in for constant when has even cardinality. Our main observation is that a of a function can be used to speed up the computation of -Convolution, and we show that an appropriate cyclic partition exists for every . Furthermore, we demonstrate that a single entry of the -Convolution can be computed more efficiently. In this variant, we are given two functions alongside with a vector and the task of the -Query problem is to compute integer . This is a generalization of the well-known Orthogonal Vectors problem. We show that -Query can be computed in time, where is the exponent of currently fastest matrix multiplication algorithm.

Fradkin and Seymour (J Comb Theory Ser B 110:19-46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk (in: Proceedings of the Algorithms-ESA 2013-21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013, pp. 505-516, 2013), where to get the desired algorithms, it is enough to bound the number of -cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of -cuts in transitive tournaments). Specifically, our main technical contribution is a combinatorial result that proves that the yes-instances of the problems (defined above) have a sub-exponential number of -cuts. We prove this bound by using a combination of chromatic coding, inductive reasoning and exploiting the structural properties of these digraphs.

For sets of points, even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least different plane perfect matchings, where is the /2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have crossings. We show the following results. (1) For every , any set with points, sufficiently large, admits a perfect matching with exactly crossings. (2) There exist sets of  points where every perfect matching has at most crossings. (3) The number of perfect matchings with at most crossings is superexponential in if is superlinear in . (4) Point sets in convex position minimize the number of perfect matchings with at most crossings for , and maximize the number of perfect matchings with crossings and with crossings.

For a set of points in the plane and a real number , let be the graph defined on by connecting each pair of points at distance at most .We consider the connectivity of in the best scenario when the location of a few of the points is uncertain, but we know for each uncertain point a line segment that contains it. More precisely, we consider the following optimization problem: given a set of points in the plane and a set of line segments in the plane, find the minimum with the property that we can select one point for each segment and the corresponding graph is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in time, for a computable function . This implies that the problem is FPT when parameterized by . The best previous algorithm uses time and computes the solution up to fixed precision.

Tree-cut width is a parameter that has been introduced as an attempt to obtain an analogue of treewidth for edge cuts. Unfortunately, in spite of its desirable structural properties, it turned out that tree-cut width falls short as an edge-cut based alternative to treewidth in algorithmic aspects. This has led to the very recent introduction of a simple edge-based parameter called edge-cut width [WG 2022], which has precisely the algorithmic applications one would expect from an analogue of treewidth for edge cuts, but does not have the desired structural properties. In this paper, we study a variant of tree-cut width obtained by changing the threshold for so-called thin nodes in tree-cut decompositions from 2 to 1. We show that this "slim tree-cut width" satisfies all the requirements of an edge-cut based analogue of treewidth, both structural and algorithmic, while being less restrictive than edge-cut width. Our results also include an alternative characterization of slim tree-cut width via an easy-to-use spanning-tree decomposition akin to the one used for edge-cut width, a characterization of slim tree-cut width in terms of forbidden immersions as well as approximation algorithm for computing the parameter.

We consider two variants of on graphs. In these games, two players alternate colouring uncoloured vertices (from a choice of colours) of a pair of isomorphic graphs while respecting the properness and the orthogonality of the partial colourings. In the , the first player unable to move loses. In the , each player aims to maximise their , which is the number of coloured vertices in their copy of the graph. We prove that, given an instance with partial colourings, both the normal play and the scoring variant of the game are PSPACE-complete. An involution of a graph is if its fixed point set induces a clique and for any non-fixed point . Andres et al. (Theor Comput Sci 795:312-325, 2019) gave a solution of the normal play variant played on graphs that admit a strictly matched involution. We prove that recognising graphs that admit a strictly matched involution is NP-complete.

An instance of the non-preemptive tree packing problem consists of an undirected graph together with a weight () for every edge . The goal is to activate every edge for some time interval of length (), such that the activated edges keep connected for the longest possible overall time. We derive a variety of results on this problem. The problem is strongly NP-hard even on graphs of treewidth 2, and it does not allow a polynomial time approximation scheme (unless P=NP). Furthermore, we discuss the performance of a simple greedy algorithm, and we construct and analyze a number of parameterized and exact algorithms.

We study a natural variant of scheduling that we call : in this variant an instance of a scheduling problem along with an integer  is given and one seeks an optimal schedule where not all, but only jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type or exist for a function that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in , -complete and fixed-parameter tractable by , or -hard parameterized by . Second, for many interesting cases we further investigate the runtime on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where is the graph with precedence constraints.

We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order- mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order- mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order -shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.

We initiate the parameterized complexity study of minimum -spanner problems on directed graphs. For a positive integer , a multiplicative -spanner of a (directed) graph is a spanning subgraph such that the distance between any two vertices in is at most times the distance between these vertices in , that is, keeps the distances in up to the distortion (or stretch) factor . An additive -spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter , that is, the distances in and differ by at most . The task of Directed Multiplicative Spanner is, given a directed graph with arcs and positive integers and , decide whether has a multiplicative -spanner with at most arcs. Similarly, Directed Additive Spanner asks whether has an additive -spanner with at most arcs. We show that (i) Directed Multiplicative Spanner admits a polynomial kernel of size and can be solved in randomized time, (ii) the weighted variant of Directed Multiplicative Spanner can be solved in time on directed acyclic graphs, (iii) Directed Additive Spanner is -hard when parameterized by for every fixed even when the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is when parameterized by and .

The Set Packing problem is, given a collection of sets over a ground set , to find a maximum collection of sets that are pairwise disjoint. The problem is among the most fundamental NP-hard optimization problems that have been studied extensively in various computational regimes. The focus of this work is on parameterized complexity, Parameterized Set Packing (PSP): Given parameter , is there a collection such that the sets in are pairwise disjoint? Unfortunately, the problem is not fixed parameter tractable unless , and, in fact, an "enumerative" running time of is required unless the exponential time hypothesis (ETH) fails. This paper is a quest for tractable instances of Set Packing from parameterized complexity perspectives. We say that the input is "compact" if , for some . In the Compact PSP problem, we are given a compact instance of PSP. In this direction, we present a "dichotomy" result of PSP: When , PSP is in FPT, while for , the problem is W[1]-hard; moreover, assuming ETH, Compact PSP does not admit time algorithm even when . Although certain results in the literature imply hardness of compact versions of related problems such as Set -Covering and Exact -Covering, these constructions fail to extend to Compact PSP. A novel contribution of our work is the identification and construction of a gadget, which we call Compatible Intersecting Set System pair, that is crucial in obtaining the hardness result for Compact PSP. Finally, our framework can be extended to obtain improved running time lower bounds for Compact -VectorSum.