Search

Recent theoretical research has shown that self-adjusting and self-adaptive mechanisms can provably outperform static settings in evolutionary algorithms for binary search spaces. However, the vast majority of these studies focuses on unimodal functions which do not require the algorithm to flip several bits simultaneously to make progress. In fact, existing self-adjusting algorithms are not designed to detect local optima and do not have any obvious benefit to cross large Hamming gaps. We suggest a mechanism called stagnation detection that can be added as a module to existing evolutionary algorithms (both with and without prior self-adjusting algorithms). Added to a simple (1+1) EA, we prove an expected runtime on the well-known Jump benchmark that corresponds to an asymptotically optimal parameter setting and outperforms other mechanisms for multimodal optimization like heavy-tailed mutation. We also investigate the module in the context of a self-adjusting (1+$\lambda$) EA and show that it combines the previous benefits of this algorithm on unimodal problems with more efficient multimodal optimization. To explore the limitations of the approach, we additionally present an example where both self-adjusting mechanisms, including stagnation detection, do not help to find a beneficial setting of the mutation rate. Finally, we investigate our module for stagnation detection experimentally., Comment: 26 pages. Full version of a paper appearing at GECCO 2020

An $H$-free editing problem asks whether we can edit at most $k$ edges to make a graph contain no induced copy of the fixed graph $H$. We obtain a polynomial kernel for this problem when $H$ is a diamond. The incompressibility dichotomy for $H$ being a 3-connected graph and the classical complexity dichotomy suggest that except for $H$ being a complete/empty graph, $H$-free editing problems admit polynomial kernels only for a few small graphs $H$. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of $H$-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.

We consider the approximate minimum selection problem in presence of independent random comparison faults. This problem asks to select one of the smallest k elements in a linearly-ordered collection of n elements by only performing unreliable pairwise comparisons: whenever two elements are compared, there is a small probability that the wrong comparison outcome is observed. We design a randomized algorithm that solves this problem with a success probability of at least 1−q for q∈(0,n−kn) and any k∈[1,n−1] using O(nk⌈log1q⌉) comparisons in expectation (if k≥n or q≥n−kn the problem becomes trivial). Then, we prove that the expected number of comparisons needed by any algorithm that succeeds with probability at least 1−q must be Ω(nklog1q) whenever q is bounded away from n−kn, thus implying that the expected number of comparisons performed by our algorithm is asymptotically optimal in this range. Moreover, we show that the approximate minimum selection problem can be solved using O((nk+loglog1q)log1q) comparisons in the worst case, which is optimal when q is bounded away from n−kn and k=O(nloglog1q)., Algorithmica, 84, ISSN:0178-4617, ISSN:1432-0541

Given a simple connected graph $G = (V, E)$, we seek to partition the vertex set $V$ into $k$ non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these $k$ parts is minimized. We refer this problem to as {\em min-max balanced connected graph partition} into $k$ parts and denote it as {\sc $k$-BGP}. The general vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm; the vertex-weighted {\sc $2$-BGP} and {\sc $3$-BGP} admit a $5/4$-approximation and a $3/2$-approximation, respectively; but no approximability result exists for {\sc $k$-BGP} when $k \ge 4$, except a trivial $k$-approximation. In this paper, we present another $3/2$-approximation for our cardinality {\sc $3$-BGP} and then extend it to become a $k/2$-approximation for {\sc $k$-BGP}, for any constant $k \ge 3$. Furthermore, for {\sc $4$-BGP}, we propose an improved $24/13$-approximation. To these purposes, we have designed several local improvement operations, which could be useful for related graph partition problems., Comment: 23 pages, 7 figures, accepted for presentation at COCOA 2019 (Xiamen, China)

We study a security game over a network played between adefenderandkattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of$$\lambda $$λnodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizingdefense-optimalnetworks which allow for the bestequilibrium defense ratio; this is the ratio ofkover the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for$$\lambda $$λconstantly close to 1 orn. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is$${\mathtt {NP}}$$NP-hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for thePrice of Defensefor any$$\lambda $$λ; this is the worst equilibrium defense ratio over all graphs.

31st International Workshop on Combinatorial Algorithms, IWOCA 2020, online, 8 Jun 2020 - 10 Jun 2020; Algorithmica : an international journal in computer science (2021). doi:10.1007/s00453-021-00840-9 special issue: "Special Issue on Combinatorial Algorithms (IWOCA 2020)", Published by Springer, New York, NY

Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to m identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that Greedy is $$(2-1/m)$$ ( 2 - 1 / m ) -competitive. The best deterministic online algorithm currently known achieves a competitive ratio of 1.9201. No deterministic online strategy can obtain a competitiveness smaller than 1.88. In this paper, we study online makespan minimization in the popular random-order model, where the jobs of a given input arrive as a random permutation. It is known that Greedy does not attain a competitive factor asymptotically smaller than 2 in this setting. We present the first improved performance guarantees. Specifically, we develop a deterministic online algorithm that achieves a competitive ratio of 1.8478. The result relies on a new analysis approach. We identify a set of properties that a random permutation of the input jobs satisfies with high probability. Then we conduct a worst-case analysis of our algorithm, for the respective class of permutations. The analysis implies that the stated competitiveness holds not only in expectation but with high probability. Moreover, it provides mathematical evidence that job sequences leading to higher performance ratios are extremely rare, pathological inputs. We complement the results by lower bounds, for the random-order model. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 4/3. Moreover, no deterministic online algorithm can attain a competitiveness smaller than 3/2 with high probability.

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work., LIPIcs, Vol. 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 30:1-30:18

Numerous combinatorial optimization problems (knapsack, maximum-weight matching, etc.) can be expressed as subset maximization problems: One is given a ground set $$N=\{1,\dots ,n\}$$ , a collection $$\mathcal {F}\subseteq 2^N$$ of subsets thereof such that $$\emptyset \in \mathcal {F}$$ , and an objective (profit) function $$p:\mathcal {F}\rightarrow \mathbb {R}_+$$ . The task is to choose a set $$S\in \mathcal {F}$$ that maximizes p(S). We consider the multistage version (Eisenstat et al., Gupta et al., both ICALP 2014) of such problems: The profit function $$p_t$$ (and possibly the set of feasible solutions $$\mathcal {F}_t$$ ) may change over time. Since in many applications changing the solution is costly, the task becomes to find a sequence of solutions that optimizes the trade-off between good per-time solutions and stable solutions taking into account an additional similarity bonus. As similarity measure for two consecutive solutions, we consider either the size of the intersection of the two solutions or the difference of n and the Hamming distance between the two characteristic vectors. We study multistage subset maximization problems in the online setting, that is, $$p_t$$ (along with possibly $$\mathcal {F}_t$$ ) only arrive one by one and, upon such an arrival, the online algorithm has to output the corresponding solution without knowledge of the future. We develop general techniques for online multistage subset maximization and thereby characterize those models (given by the type of data evolution and the type of similarity measure) that admit a constant-competitive online algorithm. When no constant competitive ratio is possible, we employ lookahead to circumvent this issue. When a constant competitive ratio is possible, we provide almost matching lower and upper bounds on the best achievable one.

The fundamental inverse problem in distance geometry is the one of finding positions from inter-point distances. The Discretizable Molecular Distance Geometry Problem (DMDGP) is a subclass of the Distance Geometry Problem (DGP) whose search space can be discretized and represented by a binary tree, which can be explored by a Branch-and-Prune (BP) algorithm. It turns out that this combinatorial search space possesses many interesting symmetry properties that were studied in the last decade. In this paper, we present a new algorithm for this subclass of the DGP, which exploits DMDGP symmetries more effectively than its predecessors. Computational results show that the speedup, with respect to the classic BP algorithm, is considerable for sparse DMDGP instances related to protein conformation.

Durand de Gevigney and Szigeti (J Gr Theory 91(4):305–325, 2019) have recently given a min–max theorem for the (2, k)-connectivity augmentation problem. This article provides an $$O(n^3(m+ n \text { }\log \text { }n))$$ time algorithm to find an optimal solution for this problem.

We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary $$\mathsf {D}$$ in fragments of a given string T of length n. The dictionary is internal in the sense that each pattern in $$\mathsf {D}$$ is given as a fragment of T. This way, $$\mathsf {D}$$ takes space proportional to the number of patterns $$d=|\mathsf {D}|$$ rather than their total length, which could be $$\varTheta (n\cdot d)$$ . In particular, we consider the following types of queries: reporting and counting all occurrences of patterns from $$\mathsf {D}$$ in a fragment $$T[i \mathinner {.\,.}j]$$ and reporting distinct patterns from $$\mathsf {D}$$ that occur in $$T[i \mathinner {.\,.}j]$$ . We show how to construct, in $$O((n+d) \log ^{O(1)} n)$$ time, a data structure that answers each of these queries in time $$O(\log ^{O(1)} n+| output |)$$ . The case of counting patterns is much more involved and needs a combination of a locally consistent parsing with orthogonal range searching. Reporting distinct patterns, on the other hand, uses the structure of maximal repetitions in strings. Finally, we provide tight—up to subpolynomial factors—upper and lower bounds for the case of a dynamic dictionary.

In this paper, we study the convex-straight-skeleton Voronoi diagrams of line segments and convex polygons. We explore the combinatorial complexity of these diagrams, and provide efficient algorithms for computing compact representations of them.

For any fixed graph $G$, the subgraph isomorphism problem asks whether an $n$-vertex input graph has a subgraph isomorphic to $G$. A well-known algorithm of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored" version of the problem, denoted $G$-$\mathsf{SUB}$, and then solves $G$-$\mathsf{SUB}$ in time $O(n^{tw(G)+1})$ where $tw(G)$ is the treewidth of $G$. Marx (2010) conjectured that $G$-$\mathsf{SUB}$ requires time $\Omega(n^{\mathrm{const}\cdot tw(G)})$ and, assuming the Exponential Time Hypothesis, proved a lower bound of $\Omega(n^{\mathrm{const}\cdot emb(G)})$ for a certain graph parameter $emb(G) \ge \Omega(tw(G)/\log tw(G))$. With respect to the size of $\mathrm{AC}^0$ circuits solving $G$-$\mathsf{SUB}$ in the average case, Li, Razborov and Rossman (2017) proved (unconditional) upper and lower bounds of $O(n^{2\kappa(G)+\mathrm{const}})$ and $\Omega(n^{\kappa(G)})$ for a different graph parameter $\kappa(G) \ge \Omega(tw(G)/\log tw(G))$. Our contributions are as follows. First, we prove that $emb(G)$ is $O(\kappa(G))$ for all graphs $G$. Next, we show that $\kappa(G)$ can be asymptotically less than $tw(G)$; for example, if $G$ is a hypercube then $\kappa(G)$ is $\Theta\big(tw(G)\big/\sqrt{\log tw(G)}\big)$. This implies that the average-case complexity of $G$-$\mathsf{SUB}$ is $n^{o(tw(G))}$ when $G$ is a hypercube. Finally, we construct $\mathrm{AC}^0$ circuits of size $O(n^{\kappa(G)+\mathrm{const}})$ that solve $G$-$\mathsf{SUB}$ in the average case, closing the gap between the upper and lower bounds of Li et al., Comment: 31 pages. International Symposium on Parameterized and Exact Computation (IPEC) 2019

Consider a set $$P\subseteq \mathbb {R}^d$$ of n points, and a convex body $$C$$ provided via a separation oracle. The task at hand is to decide for each point of $$P$$ if it is in $$C$$ using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using queries, where is the size of the largest subset of points of $$P$$ in convex position. In 2D, we provide an algorithm that efficiently generates these adaptive queries. Furthermore, we show that in two dimensions one can solve this problem using oracle queries, where is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if $$C$$ contains all points of $$P$$ . As an application of the above, we show that the discrete geometric median of a point set P in $$\mathbb {R}^2$$ can be computed in expected time.

Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of length $n$ contains a given pattern of length $k$. In this work we give two new algorithms for this well-studied problem, one whose running time is $n^{k/4 + o(k)}$, and a polynomial-space algorithm whose running time is the better of $O(1.6181^n)$ and $O(n^{k/2 + 1})$. These results improve the earlier best bounds of $n^{0.47k + o(k)}$ and $O(1.79^n)$ due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when $k \in \Omega(\log{n})$. We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. Our algorithms can also count, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time $f(k) \cdot n^{o(k/\log{k})}$ would contradict the exponential-time hypothesis (ETH). For some special classes of patterns we obtain improved running times. We further prove that $3$-increasing and $3$-decreasing permutations can, in some sense, embed arbitrary permutations of almost linear length, which indicates that an algorithm with sub-exponential running time is unlikely, even for patterns from these restricted classes., Comment: supersedes arXiv:1902.08809, with possible text overlap

This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set $E$ and $k$ weighted matroids $(E, \mathcal{I}_i, w_i)$, $i = 1, \dots, k$, and our task is to find a minimum partition $(I_1,\dots,I_k)$ of $E$ such that $I_i \in \mathcal{I}_i$ for all $i$. For each objective function, we give a polynomial-time algorithm or prove NP-hardness. In particular, for the case when the given weighted matroids are identical and the objective function is the sum of the maximum weight in each set (i.e., $\sum_{i=1}^k\max_{e\in I_i}w_i(e)$), we show that the problem is strongly NP-hard but admits a PTAS., Comment: 16 pages

We investigate the effect of crossover in the context of parameterized complexity on a well-known fixed-parameter tractable combinatorial optimization problem known as the closest string problem. We prove that a multi-start ( $$\mu$$ +1) GA solves arbitrary length-n instances of closest string in $$2^{O(d^2 + d \log k)} \cdot t(n)$$ steps in expectation. Here, k is the number of strings in the input set, d is the value of the optimal solution, and $$n \le t(n) \le {\text {poly}}(n)$$ is the number of iterations allocated to the ( $$\mu$$ +1) GA before a restart, which can be an arbitrary polynomial in n. This confirms that the multi-start ( $$\mu$$ +1) GA runs in randomized fixed-parameter tractable (FPT) time with respect to the above parameterization. On the other hand, if the crossover operation is disabled, we show there exist instances that require $$n^{\varOmega (\log (d+k))}$$ steps in expectation. The lower bound asserts that crossover is a necessary component in the FPT running time.

In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determine the eternal domination number $$\gamma ^{\infty }_{all}$$ of a graph, which is the minimum number of guards required to defend against an infinite sequence of attacks. This paper first continues the study of the eternal domination game on strong grids $$P_n\boxtimes P_m$$ . Cartesian grids $$P_n \square P_m$$ have been vastly studied with tight bounds existing for small grids such as $$k\times n$$ grids for $$k\in \{2,3,4,5\}$$ . It was recently proven that $$\gamma ^{\infty }_{all}(P_n \square P_m)=\gamma (P_n \square P_m)+O(n+m)$$ where $$\gamma (P_n \square P_m)$$ is the domination number of $$P_n \square P_m$$ which lower bounds the eternal domination number [Lamprou et al. Eternally dominating large grids. Theoretical Computer Science, 794:27–46, 2019]. We prove that, for all $$n,m\in \mathbb {N^*}$$ such that $$m\ge n$$ , $$\lfloor \frac{n}{3} \rfloor \lfloor \frac{m}{3} \rfloor +\Omega (n+m)=\gamma _{all}^{\infty } (P_{n}\boxtimes P_{m})=\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil + O(m\sqrt{n})$$ (note that $$\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil$$ is the domination number of $$P_n\boxtimes P_m$$ ). We then generalise our technique to prove that $$\gamma _{all}^{\infty }(G)=\gamma (G)+o(\gamma (G))$$ for all graphs $$G\in {\mathcal {F}}$$ , where $${\mathcal {F}}$$ is a large family of D-dimensional grids which are supergraphs of the D-dimensional Cartesian grid and subgraphs of the D-dimensional strong grid. In particular, $${\mathcal {F}}$$ includes both the D-dimensional Cartesian grid and the D-dimensional strong grid.

In this paper, we study online algorithms for the Canadian Traveller Problem defined by Papadimitriou and Yannakakis in 1991. This problem involves a traveller who knows the entire road network in advance, and wishes to travel as quickly as possible from a source vertex s to a destination vertex t, but discovers online that some roads are blocked (e.g., by snow) once reaching them. Achieving a bounded competitive ratio for the problem is PSPACE-complete. Furthermore, if at most k roads can be blocked, the optimal competitive ratio for a deterministic online algorithm is $$2k+1$$ 2 k + 1 , while the only randomized result known so far is a lower bound of $$k+1$$ k + 1 . We show, for the first time, that a polynomial time randomized algorithm can outperform the best deterministic algorithms when there are at least two blockages, and surpass the lower bound of $$2k+1$$ 2 k + 1 by an o(1) factor. Moreover, we prove that the randomized algorithm can achieve a competitive ratio of $$\big (1+ \frac{\sqrt{2}}{2} \big )k + \sqrt{2}$$ ( 1 + 2 2 ) k + 2 in pseudo-polynomial time. The proposed techniques can also be exploited to implicitly represent multiple near-shortest s-t paths.

In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$ NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$ NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$ c > 1 , Matching Cut is $${\mathsf {NP}}$$ NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ ϵ > 0 , Matching Cut remains $${\mathsf {NP}}$$ NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$ δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree $$\delta \ge 3$$ δ ≥ 3 in $$O^*(\lambda ^n)$$ O ∗ ( λ n ) time, where $$\lambda$$ λ is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$ x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$ O ∗ ( 1 . 0099 n ) on graphs with minimum degree $$\delta \ge 469$$ δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants $$1< c 1 < c < 4 and $$c^{\prime }\ge 0$$ c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$ δ ≥ 1 c n - c ′ .

In the last decade remarkable progress has been made in development of suitable proof techniques for analysing randomised search heuristics. The theoretical investigation of these algorithms on classes of functions is essential to the understanding of the underlying stochastic process. Linear functions have been traditionally studied in this area resulting in tight bounds on the expected optimisation time of simple randomised search algorithms for this class of problems. Recently, the constrained version of this problem has gained attention and some theoretical results have also been obtained on this class of problems. In this paper we study the class of linear functions under uniform constraint and investigate the expected optimisation time of Randomised Local Search (RLS) and a simple evolutionary algorithm called (1+1) EA. We prove a tight bound of $\Theta(n^2)$ for RLS and improve the previously best known upper bound of (1+1) EA from $O(n^2 \log (Bw_{\max}))$ to $O(n^2\log B)$ in expectation and to $O(n^2 \log n)$ with high probability, where $w_{\max}$ and $B$ are the maximum weight of the linear objective function and the bound of the uniform constraint, respectively. Also, we obtain a tight bound of $O(n^2)$ for the (1+1) EA on a special class of instances. We complement our theoretical studies by experimental investigations that consider different values of $B$ and also higher mutation rates that reflect the fact that $2$-bit flips are crucial for dealing with the uniform constraint., Comment: Journal version to appear in Algorithmica

Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. https://doi.org/10.1145/3265027 ) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). Here, we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (Sim-FES). In this problem, the input is an n-vertex graph G, a positive integer k, and a coloring function col: $$E(G) \rightarrow 2^{[\alpha ]}$$ , and the objective is to check whether there is an edge subset S of cardinality k in G such that for each $$i \in [\alpha ]$$ , $$G_i - S$$ is acyclic. Unlike the vertex variant of the problem, when $$\alpha =1$$ , the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for $$\alpha =3$$ , Sim-FES is NP-hard, and does not admit an algorithm of running time $$2^{o(k)}n^{{{\mathcal {O}}}(1)}$$ unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time $$2^{\omega k \alpha +\alpha \log k} n^{{{\mathcal {O}}}(1)}$$ where $$\omega$$ is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when $$\alpha =2$$ . We also give a kernel for Sim-FES with $$(k\alpha )^{{\mathcal {O}}(\alpha )}$$ vertices. Finally, we consider a “dual” version of the problem called Maximum Simultaneous Acyclic Subgraph and give an FPT algorithm with running time $$2^{\omega q \alpha }n^{{\mathcal {O}}(1)}$$ , where q is the number of edges in the output subgraph.

Obvious strategyproofness (OSP) is an appealing concept as it allows to maintain incentive compatibility even in the presence of agents that are not fully rational, i.e., those who struggle with contingent reasoning (Li in Am Econ Rev 107(11):3257–3287, 2017). However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching (Ashlagi and Gonczarowski in J Econ Theory 177:405–425, 2018). We here deepen the study of the limitations of OSP mechanisms by looking at their approximation guarantees for basic optimization problems paradigmatic of the area, i.e., machine scheduling and facility location. We prove a number of bounds on the approximation guarantee of OSP mechanisms, which show that OSP can come at a significant cost. However, rather surprisingly, we prove that OSP mechanisms can return optimal solutions when they use monitoring—a novel mechanism design paradigm that introduces a mild level of scrutiny on agents’ declarations (Kovács et al. in WINE 9470:398–412, 2015).

In this article, we study some fault-tolerant covering problems in metric spaces. In the metric multi-cover problem (MMC), we are given two point sets Y (servers) and X (clients) in an arbitrary metric space $$(X \cup Y, d)$$ , a positive integer k that represents the coverage demand of each client, and a constant $$\alpha \ge 1$$ . Each server can host a single ball of arbitrary radius centered on it. Each client $$x \in X$$ needs to be covered by at least k such balls centered on servers. The objective function that we wish to minimize is the sum of the $$\alpha $$ -th powers of the radii of the balls. We also study some non-trivial generalizations of the MMC, such as (a) the non-uniform MMC, where we allow client-specific demands, and (b) the t-MMC, where we require the number of open servers to be at most some given integer t. We present the first constant approximations for these fault-tolerant covering problems. Our algorithms are based on the following paradigm: for each of the three problems, we present an efficient algorithm that reduces the problem to several instances of the corresponding 1-covering problem, where the coverage demand of each client is 1. The reductions preserve optimality up to a multiplicative constant factor. Applying known constant factor approximation algorithms for 1-covering, we obtain our results for the MMC and these generalizations.

There exist many variants of guarding an orthogonal polygon in an orthogonal fashion: sometimes a guard can see within a rectangle, along a staircase, or along an orthogonal path with at most k bends. In this paper, we study all these guarding models for the special case of orthogonal polygons that have bounded treewidth in some sense. As our main result, we show that the problem of finding the minimum number of guards in all these models becomes linear-time solvable on polygons with bounded treewidth. We complement our main result by giving some hardness results.

Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice. We introduce p-linear colorings as an alternative to the commonly used p-centered colorings. They can be efficiently computed in bounded expansion classes and use at most as many colors as p-centered colorings. Although a set of $$k k < p colors from a p-centered coloring induces a subgraph of treedepth at most k, the same number of colors from a p-linear coloring may induce subgraphs of larger treedepth. We establish a polynomial upper bound on the treedepth in general graphs, and give tighter bounds in trees and interval graphs via constructive coloring algorithms. We also give a co-NP-completeness reduction for recognizing p-linear colorings and discuss ways to overcome this limitation in practice.

Traditionally, computation within self-assembly models is hard to conceal because the self-assembly process generates a crystalline assembly whose computational history is inherently part of the structure itself. With no way to remove information from the computation, this computational model offers a unique problem: how can computational input and computation be hidden while still computing and reporting the final output? Designing such systems is inherently motivated by privacy concerns in biomedical computing and applications in cryptography. In this paper we propose the problem of performing ``covert computation'' within tile self-assembly that seeks to design self-assembly systems that ``conceal'' both the input and computational history of performed computations. We achieve these results within the growth-only restricted abstract Tile Assembly Model (aTAM) with positive and negative interactions. We show that general-case covert computation is possible by implementing a set of basic covert logic gates capable of simulating any circuit (functionally complete). To further motivate the study of covert computation, we apply our new framework to resolve an outstanding complexity question; we use our covert circuitry to show that the unique assembly verification problem within the growth-only aTAM with negative interactions is coNP-complete., Short version published at the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

We resolve a number of long-standing open problems in online graph coloring. More specifically, we develop tight lower bounds on the performance of online algorithms for fundamental graph classes. An important contribution is that our bounds also hold for randomized online algorithms, for which hardly any results were known. Technically, we construct lower bounds for chordal graphs. The constructions then allow us to derive results on the performance of randomized online algorithms for the following further graph classes: trees, planar, bipartite, inductive, bounded-treewidth and disk graphs. It shows that the best competitive ratio of both deterministic and randomized online algorithms is $$\Theta (\log n)$$ Θ ( log n ) , where n is the number of vertices of a graph. Furthermore, we prove that this guarantee cannot be improved if an online algorithm has a lookahead of size $$O(n/\log n)$$ O ( n / log n ) or access to a reordering buffer of size $$n^{1-\epsilon }$$ n 1 - ϵ , for any $$0 0 < ϵ ≤ 1 . A consequence of our results is that, for all of the above mentioned graph classes except bipartite graphs, the natural First Fit coloring algorithm achieves an optimal performance, up to constant factors, among deterministic and randomized online algorithms.

We study the problem of enumerating the $k$-arc-connected orientations of a graph $G$, i.e., generating each exactly once. A first algorithm using submodular flow optimization is easy to state, but intricate to implement. In a second approach we present a simple algorithm with $O(knm^2)$ time delay and amortized time $O(m^2)$, which improves over the analysis of the submodular flow algorithm. As ingredients, we obtain enumeration algorithms for the $\alpha$-orientations of a graph $G$ in $O(m^2)$ time delay and for the outdegree sequences attained by $k$-arc-connected orientations of $G$ in $O(knm^2)$ time delay., Comment: 13 pages, 1 Figure, corrected typos

For an integer t, we let $$P_t$$ denote the t-vertex path. We write $$H+G$$ for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that a graph G is H-free if no induced subgraph of G is isomorphic to the graph H. In this paper, we study the complexity of k-coloring, for a fixed integer k, when restricted to the class of H-free graphs with a fixed graph H. We provide a polynomial-time algorithm to test if, for fixed r, a $$(P_6+rP_3)$$ -free is three-colorable, and find a coloring if one exists. We also solve the list version of this problem, where each vertex is assigned a list of possible colors, which is a subset of $$\{1,2,3\}$$ . This generalizes results of Broersma, Golovach, Paulusma, and Song, and results of Klimosova, Malik, Masařik, Novotna, Paulusma, and Slivova. Our proof uses a result of Ding, Seymour, and Winkler relating matchings and hitting sets in hypergraphs. We also prove that the problem of deciding if a $$(P_5+P_2)$$ -free graph has a k-coloring is NP-hard for every fixed $$k \ge 5$$ .

Applications designed for data-parallel computation frameworks such as MapReduce usually alternate between computation and communication stages. Coflow scheduling is a recent popular networking abstraction introduced to capture such application-level communication patterns in datacenters. In this framework, a datacenter is modeled as a single non-blocking switch with m input ports and m output ports. A coflow j is a collection of flow demands \(\{d^j_{io}\}_{i \in m, o \in m}\) that is said to be complete once all of its requisite flows have been scheduled.

It is generally accepted that populations are useful for the global exploration of multi-modal optimisation problems. Indeed, several theoretical results are available showing such advantages over single-trajectory search heuristics. In this paper we provide evidence that evolving populations via crossover and mutation may also benefit the optimisation time for hillclimbing unimodal functions. In particular, we prove bounds on the expected runtime of the standard ($$\mu +1$$ μ + 1 ) GA for OneMax that are lower than its unary black box complexity and decrease in the leading constant with the population size up to $$\mu =o\left( \sqrt{\log n}\right) $$ μ = o log n . Our analysis suggests that the optimal mutation strategy is to flip two bits most of the time. To achieve the results we provide two interesting contributions to the theory of randomised search heuristics: (1) A novel application of drift analysis which compares absorption times of different Markov chains without defining an explicit potential function. (2) The inversion of fundamental matrices to calculate the absorption times of the Markov chains. The latter strategy was previously proposed in the literature but to the best of our knowledge this is the first time is has been used to show non-trivial bounds on expected runtimes.

Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of evolutionary algorithms which use non-trivial populations remains challenging and only few rigorous results exist. Already for the most basic problem, the determination of the asymptotic runtime of the $(\mu+\lambda)$ evolutionary algorithm on the simple OneMax benchmark function, only the special cases $\mu=1$ and $\lambda=1$ have been solved. In this work, we analyze this long-standing problem and show the asymptotically tight result that the runtime $T$, the number of iterations until the optimum is found, satisfies \[E[T] = \Theta\bigg(\frac{n\log n}{\lambda}+\frac{n}{\lambda / \mu} + \frac{n\log^+\log^+ \lambda/ \mu}{\log^+ \lambda / \mu}\bigg),\] where $\log^+ x := \max\{1, \log x\}$ for all $x > 0$. The same methods allow to improve the previous-best $O(\frac{n \log n}{\lambda} + n \log \lambda)$ runtime guarantee for the $(\lambda+\lambda)$~EA with fair parent selection to a tight $\Theta(\frac{n \log n}{\lambda} + n)$ runtime result., Comment: 50 pages, extended version of the conference paper Denis Antipov, Benjamin Doerr, Jiefeng Fang, and Tangi Hetet Runtime analysis for the ({\mu} + {\lambda}) EA optimizing OneMax. In Genetic and Evolutionary Computation Conference, GECCO 2018, pages 1459-1466. ACM, 2018

A space bounded $$ O(d/\log d)$$ O ( d / log d ) -competitive hypercube packing algorithm with one active bin only is presented. As a starting point we give a simple 1-space bounded hypercube packing algorithm with competitive ratio $$ (3/2)^{d}+O((21/16)^d)$$ ( 3 / 2 ) d + O ( ( 21 / 16 ) d ) , for $$d\ge 3.$$ d ≥ 3 .

The $k$-leaf power graph $G$ of a tree $T$ is a graph whose vertices are the leaves of $T$ and whose edges connect pairs of leaves at unweighted distance at most~$k$ in $T$. Recognition of the $k$-leaf power graphs for $k \geq 7$ is still an open problem. In this paper, we provide two algorithms for this problem for sparse leaf power graphs. Our results shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by $k$ and by the degeneracy of the given graph. To prove this, we first describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of $k$ and the degeneracy of $G$. The first presented algorithm uses methods based on monadic second-order logic (MSO$_2$) to recognize the existence of a leaf power as a subgraph of the product graph. Using the same embedding in the product graph, the second algorithm presents a dynamic programming approach to solve the problem and provide a better dependence on the parameters.

Given a simple graph $G = (V, E)$ and a constant integer $k \ge 2$, the $k$-path vertex cover problem ({\sc P$k$VC}) asks for a minimum subset $F \subseteq V$ of vertices such that the induced subgraph $G[V - F]$ does not contain any path of order $k$. When $k = 2$, this turns out to be the classic vertex cover ({\sc VC}) problem, which admits a $\left(2 - {\rm \Theta}\left(\frac 1{\log|V|}\right)\right)$-approximation. The general {\sc P$k$VC} admits a trivial $k$-approximation; when $k = 3$ and $k = 4$, the best known approximation results for {\sc P$3$VC} and {\sc P$4$VC} are a $2$-approximation and a $3$-approximation, respectively. On $d$-regular graphs, the approximation ratios can be reduced to $\min\left\{2 - \frac 5{d+3} + \epsilon, 2 - \frac {(2 - o(1))\log\log d}{\log d}\right\}$ for {\sc VC} ({\it i.e.}, {\sc P$2$VC}), $2 - \frac 1d + \frac {4d - 2}{3d |V|}$ for {\sc P$3$VC}, $\frac {\lfloor d/2\rfloor (2d - 2)}{(\lfloor d/2\rfloor + 1) (d - 2)}$ for {\sc P$4$VC}, and $\frac {2d - k + 2}{d - k + 2}$ for {\sc P$k$VC} when $1 \le k-2 < d \le 2(k-2)$. By utilizing an existing algorithm for graph defective coloring, we first present a $\frac {\lfloor d/2\rfloor (2d - k + 2)}{(\lfloor d/2\rfloor + 1) (d - k + 2)}$-approximation for {\sc P$k$VC} on $d$-regular graphs when $1 \le k - 2 < d$. This beats all the best known approximation results for {\sc P$k$VC} on $d$-regular graphs for $k \ge 3$, except for {\sc P$4$VC} it ties with the best prior work and in particular they tie at $2$ on cubic graphs and $4$-regular graphs. We then propose a $1.875$-approximation and a $1.852$-approximation for {\sc P$4$VC} on cubic graphs and $4$-regular graphs, respectively. We also present a better approximation algorithm for {\sc P$4$VC} on $d$-regular bipartite graphs., Comment: 20 pages, 5 figures

The Maximum Carpool Matching problem is a star packing problem in directed graphs. Formally, given a directed graph $$G = (V, A)$$ , a capacity function $$c: V \rightarrow {\mathbb {N}}$$ , and a weight function $$w: A \rightarrow {\mathbb {R}}^+$$ , a carpool matching is a subset of arcs, $$M \subseteq A$$ , such that every $$v \in V$$ satisfies: (1) $$d^{\text {in}}_{M}(v) \cdot d^{\text {out}}_{M}(v) = 0$$ , (2) $$d^{\text {in}}_{M}(v) \le c(v)$$ , and (3) $$d^{\text {out}}_{M}(v) \le 1$$ . A vertex v for which $$d^{\text {out}}_{M}(v) = 1$$ is a passenger, and a vertex for which $$d^{\text {out}}_{M}(v) = 0$$ is a driver who has $$d^{\text {in}}_{M}(v)$$ passengers. In the Maximum Carpool Matching problem the goal is to find a carpool matching M of maximum total weight. The problem arises when designing an online carpool service, such as Zimride (Zimride by enterprise. https://zimride.com/ ), which tries to connect between users based on a similarity function. The problem is known to be NP-hard, even in the unweighted and uncapacitated case. The Maximum Group Carpool Matching problem, is an extension of the Maximum Carpool Matching where each vertex represents an unsplittable group of passengers. Formally, each vertex $$u \in V$$ has a size $$s(u) \in {\mathbb {N}}$$ , and the constraint $$d^{\text {in}}_{M}(v) \le c(v)$$ is replaced with $$\sum _{u:(u,v) \in M} s(u) \le c(v)$$ . We show that Maximum Carpool Matching can be formulated as an unconstrained submodular maximization problem, thus it admits a $$\frac{1}{2}$$ -approximation algorithm. We show that the same formulation does not work for Maximum Group Carpool Matching, nevertheless, we present a local search $$(\frac{1}{2} - \varepsilon )$$ -approximation algorithm for Maximum Group Carpool Matching. For the unweighted variant of both problems when the maximum possible capacity, $$c_{\max }$$ , is bounded by a constant, we provide a local search $$(\frac{1}{2}+ \frac{1}{2c_{\max }} - \varepsilon )$$ -approximation algorithm. We also provide an APX-hardness result, even if the maximum degree and $$c_{\max }$$ are at most 3.

In this work we study the problem of collecting protected data in ad-hoc sensor network using a mobile entity called MULE. The objective is to increase information survivability in the network. Sensors from all over the network, route their sensing data through a data gathering tree, towards a particular node, called the $sink$. In case of a failed sensor, all the aggregated data from the sensor and from its children is lost. In order to retrieve the lost data, the MULE is required to travel among all the children of the failed sensor and to re-collect the data. There is a cost to travel between two points in the plane. We aim to minimize the MULE traveling cost, given that any sensor can fail. In order to reduce the traveling cost, it is necessary to find the optimal data gathering tree and the MULE location. We are considering the problem for the unit disk graphs (UDG) and Euclidean distance cost function. We propose a primal-dual algorithm that produces a $\left(20+\varepsilon\right)$-approximate solution for the problem, where $\varepsilon\rightarrow0$ as the sensor network spreads over a larger area. The algorithm requires $O\left(n^{3}\cdot\varDelta\left(G\right)\right)$ time to construct a gathering tree and to place the MULE, where $\varDelta\left(G\right)$ is the maximum degree in the graph and $n$ is the number of nodes., Comment: 27 pages, 5 figures

International audience; In the localization game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph $G$. At every step, one vertex $v$ of $G$ can be probed which results in the knowledge of the distance between $v$ and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location.We address the generalization of this game where $k\geq 1$ vertices can be probed at every step. Our game also generalizes the notion of the {\it metric dimension} of a graph.Precisely, given a graph $G$ and two integers $k,\ell \geq 1$, the {\sc Localization} problem asks whether there exists a strategy to locate a target hidden in $G$ in at most $\ell$ steps and probing at most $k$ vertices per step. We first show that, in general, this problem is \textsf{NP}-complete for every fixed $k \geq 1$ (resp., $\ell \geq 1$).We then focus on the class of trees.On the negative side,we prove that the \Localization problem is \textsf{NP}-complete in trees when $k$ and $\ell$ are part of the input. On the positive side, we design a $(+1)$-approximation algorithm for the problem in $n$-node trees, {\it i.e.}, an algorithm that computes in time $O(n \log n)$ (independent of $k$) a strategy to locate the target in at most one more step than an optimal strategy. This algorithm can be used to solve the \Localization problem in trees in polynomial time if $k$ is fixed.We also consider some of these questions in the context where, upon probing the vertices,the relative distances to the target are retrieved.This variant of the problem generalizes the notion of the {\it centroidal dimension} of a graph.

We consider the problem of designing succinct data structures for interval graphs with n vertices while supporting degree, adjacency, neighborhood and shortest path queries in optimal time. Towards showing succinctness, we first show that at least $$n\log _2{n} - 2n\log _2\log _2 n - O(n)$$ bits are necessary to represent any unlabeled interval graph G with n vertices, answering an open problem of Yang and Pippenger (Proc Am Math Soc Ser B 4(1):1–3, 2017). This is augmented by a data structure of size $$n\log _2{n} +O(n)$$ bits while supporting not only the above queries optimally but also capable of executing various combinatorial algorithms (like proper coloring, maximum independent set etc.) on interval graphs efficiently. Finally, we extend our ideas to other variants of interval graphs, for example, proper/unit interval graphs, k-improper interval graphs, and circular-arc graphs, and design succinct data structures for these graph classes as well along with supporting queries on them efficiently.

The stable matching problem is one of the central problems of algorithmic game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, even when the ties are of size two. Moreover, in this setting it is UGC-hard to provide an approximation for the maximum cardinality stable matching problem with a constant factor smaller than 4/3. In this paper, we give a tight analysis of an approximation algorithm given by Huang and Kavitha for the maximum cardinality stable matching problem with ties of size two, demonstrating an improved 4/3-approximation factor., Added a detailed comparison with the approaches from the papers "On the approximability of the stable marriage problem with one-sided ties." by Bauckholt, Pashkovich, and Sanita and "Improved approximation algorithms for two variants of the stable marriage problem with ties." by Huang and Kavitha. (See Appendix)

We study a class of multi-scenario single-machine scheduling problems. In this class of problems, we are given a set of scenarios with each one having a different realization of job characteristics. We consider these multi-scenario problems where the scheduling criterion can be any one of the following three: The total weighted completion time, the weighted number of tardy jobs, and the weighted number of jobs completed exactly at their due-date. As all the resulting problems are NP-hard, our analysis focuses on whether any one of the problems becomes tractable when some specific natural parameters are of limited size. The analysis includes the following parameters: The number of jobs with scenario-dependent processing times, the number of jobs with scenario-dependent weights, and the number of different due-dates.

In the Escherization problem, given a closed figure in the plane, the objective is to find a closed figure that is as close as possible to the input figure that tiles the plane. Koizumi and Sugihara’s formulation reduces this problem to an eigenvalue problem. In their formulation, only one of the potentially numerous templates is used to parameterize the possible tile shapes for each isohedral type. In this research, we try to search for the best tile shape using all possible templates for the nine most general isohedral types. This extension provides a considerable flexibility in possible tile shapes and improves the quality of the obtained tile shapes. However, the exhaustive search of all possible templates is computationally unrealistic using conventional calculation methods, and we develop an efficient algorithm to perform this in a reasonable computation time.

A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues, so that no two independent edges of the same queue are nested. The queue number of G is the minimum number of queues required by any queue layout of G. In this paper, we continue the study of the queue number of planar 3-trees. As opposed to general planar graphs, whose queue number is not known to be bounded by a constant, the queue number of planar 3-trees has been shown to be at most seven. In this work, we improve the upper bound to five. We also show that there exist planar 3-trees, whose queue number is at least four; this is the first example of a planar graph with queue number greater than three., Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

We show that the eccentricities, diameter, radius, and Wiener index of an undirected n-vertex graph with nonnegative edge lengths can be computed in time $$O(n\cdot \left( {\begin{array}{c}k+\lceil \log n\rceil \\ k\end{array}}\right) \cdot 2^k \log n)$$ O ( n · k + ⌈ log n ⌉ k · 2 k log n ) , where k is linear in the treewidth of the graph. For every $$\epsilon >0$$ ϵ > 0 , this bound is $$n^{1+\epsilon }\exp O(k)$$ n 1 + ϵ exp O ( k ) , which matches a hardness result of Abboud et al. (in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. 10.1137/1.9781611974331.ch28) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comput Geom 42:815–824, 2009. 10.1016/j.comgeo.2009.02.001) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form $$\log ^d n$$ log d n to $$\left( {\begin{array}{c}d+\lceil \log n\rceil \\ d\end{array}}\right)$$ d + ⌈ log n ⌉ d , as originally observed by Monier (J Algorithms 1:60–74, 1980. 10.1016/0196-6774(80)90005-X). We also investigate the parameterization by vertex cover number.

We introduce and study the maximum reliability coverage problem, where multiple facilities are to be located on a network whose arcs are subject to random failures. Our model assumes that arcs fail independently with non-uniform probabilities, and the objective is to locate a given number of facilities, aiming to maximize the expected demand serviced. In this context, each demand point is said to be serviced (or covered) when it is reachable from at least one facility by an operational path. The main contribution of this paper is to establish tight bounds on the approximability of maximum reliability coverage on bidirected trees as well as on general networks. Quite surprisingly, we show that this problem is NP-hard on bidirected trees via a carefully-constructed reduction from the partition problem. On the positive side, we make use of approximate dynamic programming ideas to devise an FPTAS on bidirected trees. For general networks, while maximum reliability coverage is $$(1 - 1/e + \epsilon )$$ -inapproximable as an extension of the max k-cover problem, even estimating its objective value is #P-complete, due to generalizing certain network reliability problems. Nevertheless, we prove that by plugging-in a sampling-based additive estimator into the standard greedy algorithm, a matching approximation ratio of $$1 - 1/e - \epsilon $$ can be attained.

In this paper, we consider the following sum query problem: Given a point set P in $${\mathbb {R}}^d$$ , and a distance-based function f(p, q) (i.e., a function of the distance between p and q) satisfying some general properties, the goal is to develop a data structure and a query algorithm for efficiently computing a $$(1+\epsilon )$$ -approximate solution to the sum $$\sum _{p \in P} f(p,q)$$ for any query point $$q \in {\mathbb {R}}^d$$ and any small constant $$\epsilon >0$$ . Existing techniques for this problem are mainly based on some core-set techniques which often have difficulties to deal with functions with local domination property. Based on several new insights to this problem, we develop in this paper a novel technique to overcome these encountered difficulties. Our algorithm is capable of answering queries with high success probability in time no more than $${\tilde{O}}_{\epsilon ,d}(n^{0.5 + c})$$ , and the underlying data structure can be constructed in $${\tilde{O}}_{\epsilon ,d}(n^{1+c})$$ time for any $$c>0$$ , where the hidden constant has only polynomial dependence on $$1/\epsilon$$ and d. Our technique is simple and can be easily implemented for practical purpose.

One method to obtain a proper vertex coloring of graphs using a reasonable number of colors is to start from any arbitrary proper coloring and then repeat some local re-coloring techniques to reduce the number of color classes. The Grundy (First-Fit) coloring and color-dominating colorings of graphs are two well-known such techniques. The color-dominating colorings are also known and commonly referred as b-colorings. But these two topics have been studied separately in graph theory. We introduce a new coloring procedure which combines the strategies of these two techniques and satisfies an additional property. We first prove that the vertices of every graph G can be effectively colored using color classes say $$C_1, \ldots , C_k$$ such that (i) for any two colors i and j with $$1\le i< j \le k$$ , any vertex of color j is adjacent to a vertex of color i, (ii) there exists a set $$\{u_1, \ldots , u_k\}$$ of vertices of G such that $$u_j\in C_j$$ for any $$j\in \{1, \ldots , k\}$$ and $$u_k$$ is adjacent to $$u_j$$ for each $$1\le j \le k$$ with $$j\not = k$$ , and (iii) for each i and j with $$i\not = j$$ , the vertex $$u_j$$ has a neighbor in $$C_i$$ . This provides a new vertex coloring heuristic which improves both Grundy and color-dominating colorings. Denote by z(G) the maximum number of colors used in any proper vertex coloring satisfying the above properties. The z(G) quantifies the worst-case behavior of the heuristic. We prove the existence of $$\{G_n\}_{n\ge 1}$$ such that $$\min \{\Gamma (G_n), b(G_n)\} \rightarrow \infty $$ but $$z(G_n)\le 3$$ for each n. For each positive integer t we construct a family of finitely many colored graphs $${{\mathcal {D}}}_t$$ satisfying the property that if $$z(G)\ge t$$ for a graph G then G contains an element from $${{\mathcal {D}}}_t$$ as a colored subgraph. This provides an algorithmic method for proving numeric upper bounds for z(G).