Given two strings A and B such that B is a permutation of A, the max duo-preservation string mapping (MPSM) problem asks to find a mapping π between them so as to preserve a maximum number of duos. A duo is any pair of consecutive characters in a string and it is preserved by π if its two consecutive characters in A are mapped to same two consecutive characters in B. This problem has received a growing attention in recent years, partly as an alternative way to produce approximation algorithms for its minimization counterpart, min common string partition, a widely studied problem due its applications in comparative genomics. Considering this favored field of application with short alphabet, it is surprising that MPSM^𝓁, the variant of MPSM with bounded alphabet, has received so little attention, with a single yet impressive work that provides a 2.67-approximation achieved in O(n) [Brubach, 2018], where n = |A| = |B|. Our work focuses on MPSM^𝓁, and our main contribution is the demonstration that this problem admits a Polynomial Time Approximation Scheme (PTAS) when 𝓁 = O(1). We also provide an alternate, somewhat simpler, proof of NP-hardness for this problem compared with the NP-hardness proof presented in [Haitao Jiang et al., 2012].

A mixed dominating set $S$ of a graph $G=(V,E)$ is a subset $ S \subseteq V \cup E$ such that each element $v\in (V \cup E) \setminus S$ is adjacent or incident to at least one element in $S$. The mixed domination number $γ_m(G)$ of a graph $G$ is the minimum cardinality among all mixed dominating sets in $G$. The problem of finding $γ_{m}(G)$ is know to be NP-complete. In this paper, we present an explicit polynomial-time algorithm to construct a mixed dominating set of size $γ_{m}(G)$ by a parse tree when $G$ is a generalized series-parallel graph.

In (k,r)-Center we are given a (possibly edge-weighted) graph and are asked to select at most k vertices (centers), so that all other vertices are at distance at most r from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically: - For any r>=1, we show an algorithm that solves the problem in O*((3r+1)^cw) time, where cw is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithm's performance. As a corollary, for r=1, this closes the gap that previously existed on the complexity of Dominating Set parameterized by cw. - We strengthen previously known FPT lower bounds, by showing that (k,r)-Center is W[1]-hard parameterized by the input graph's vertex cover (if edge weights are allowed), or feedback vertex set, even if k is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs. - We show that the complexity of the problem parameterized by tree-depth is 2^Theta(td^2) by showing an algorithm of this complexity and a tight ETH-based lower bound. We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth which work efficiently independently of the values of k,r. In particular, we give algorithms which, for any epsilon>0, run in time O*((tw/epsilon)^O(tw)), O*((cw/epsilon)^O(cw)) and return a (k,(1+epsilon)r)-center, if a (k,r)-center exists, thus circumventing the problem's W-hardness.

In this paper we focus on problems which do not admit a constant-factor approximation in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For MIN INDEPENDENT DOMINATING SET, MAX INDUCED PATH, FOREST and TREE, for any r(n), a simple, known scheme gives an approximation ratio of r in time roughly r^{n/r}. We show that, for most values of r, if this running time could be significantly improved the ETH would fail. For MAX MINIMAL VERTEX COVER we give a non-trivial sqrt{r}-approximation in time 2^{n/{r}}. We match this with a similarly tight result. We also give a log(r)-approximation for MIN ATSP in time 2^{n/r} and an r-approximation for MAX GRUNDY COLORING in time r^{n/r}. Furthermore, we show that MIN SET COVER exhibits a curious behavior in this super-polynomial setting: for any delta>0 it admits an m^delta-approximation, where m is the number of sets, in just quasi-polynomial time. We observe that if such ratios could be achieved in polynomial time, the ETH or the Projection Games Conjecture would fail.

It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS'99), that MAX-CUT admits a PTAS on dense graphs, and more generally, MAX-k-CSP admits a PTAS on "dense" instances with Omega(n^k) constraints. In this paper we extend and generalize their exhaustive sampling approach, presenting a framework for (1-epsilon)-approximating any MAX-k-CSP problem in sub-exponential time while significantly relaxing the denseness requirement on the input instance. Specifically, we prove that for any constants delta in (0, 1] and epsilon > 0, we can approximate MAX-k-CSP problems with Omega(n^{k-1+delta}) constraints within a factor of (1-epsilon) in time 2^{O(n^{1-delta}*ln(n) / epsilon^3)}. The framework is quite general and includes classical optimization problems, such as MAX-CUT, MAX-DICUT, MAX-k-SAT, and (with a slight extension) k-DENSEST SUBGRAPH, as special cases. For MAX-CUT in particular (where k=2), it gives an approximation scheme that runs in time sub-exponential in n even for "almost-sparse" instances (graphs with n^{1+delta} edges). We prove that our results are essentially best possible, assuming the ETH. First, the density requirement cannot be relaxed further: there exists a constant r < 1 such that for all delta > 0, MAX-k-SAT instances with O(n^{k-1}) clauses cannot be approximated within a ratio better than r in time 2^{O(n^{1-delta})}. Second, the running time of our algorithm is almost tight for all densities. Even for MAX-CUT there exists r<1 such that for all delta' > delta >0, MAX-CUT instances with n^{1+delta} edges cannot be approximated within a ratio better than r in time 2^{n^{1-delta'}}.

Abstract We consider a probabilistic model for the Steiner Tree problem. Under this model, the problem is defined in a two‐stage setting over a first‐stage complete weighted graph having its vertices associated with a probability of presence (independently each from another) in the second stage. A first‐stage feasible solution on the input graph might become infeasible in the second stage, when certain vertices of the graph fail. Therefore, a well defined modification strategy is devised for modifying the remainders of a first‐stage solution to render it second‐stage feasible. The objective is to minimize the expected weight of the second‐stage solution over the distribution of all possible second‐stage materializable subgraphs of the input graph. We recognize two complementary computational problems in this setting, one being the a priori computation of first‐stage decisions given a particular modification strategy, and the second being the cost‐efficient modification of a first‐stage feasible solution. We prove that both these problems are NP‐hard for the Steiner Tree problem under this setting. We design and analyze probabilistically an efficient modification strategy and derive tight approximation results for both aforementioned problems. We show that our techniques can be extended to the case of the more general Steiner Forest problem in the same probabilistic setting. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We study the probabilistic longest path problem. We propose a modification strategy adapting a solution for a deterministic instance to a solution for the probabilistic one, we compute the functional associated with this strategy, and we evaluate the complexities of computing this functional and of computing the deterministic solution maximizing it. © 1999 John Wiley & Sons, Inc. Networks 33: 207–219, 1999

A Boltzmann machine architecture to solve the problems of maximum independent set, set partitioning, clique, minimum vertex cover, minimum set cover, and maximum set packing is described. The authors evaluate the maximum and the average error of the method where the error is defined as the ratio of the cardinality of the obtained solution for an instance with respect to the optimal one. The results are compared with those obtained from the implementation of the heuristic described by D.S. Johnson (1974). The model treats the general case of all these problems that is the case when costs are associated with the data (vertices or subsets). The unweighted case becomes a particular case in this approach. It is shown that the model finds optimal solutions for a large percentage of the treated instances and provides a good performance ratio for the rest.>