The problem of computing the longest common subsequence of two sequences ( LCS for short) is a classical and fundamental problem in computer science. In this article, we study four variants of LCS : the Repetition-Bounded Longest Common Subsequence problem ( RBLCS ), the Multiset-Restricted Common Subsequence problem ( MRCS ), the Two-Side-Filled Longest Common Subsequence problem ( 2FLCS ), and the One-Side-Filled Longest Common Subsequence problem ( 1FLCS ). Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O ( 1 . 4422 5 n ) -time, dynamic programming (DP) based algorithm for RBLCS was proposed, where the two input sequences have lengths n and p o l y ( n ) . Here, we first establish that each of MRCS , 1FLCS , and 2FLCS is polynomially equivalent to RBLCS . Then, we design a refined DP-based algorithm for RBLCS that runs in O ( 1 . 4142 2 n ) time, which implies that MRCS , 1FLCS , and 2FLCS can also be solved in O ( 1 . 4142 2 n ) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS .

In this paper, we study a type of incremental optimization variant of the Maximum Independent Set problem (MaxIS), called Bounded-Deletion Maximum Independent Set problem (BD-MaxIS): Given an unweighted graph $$G = (V, E)$$ , an initial feasible solution (i.e., an independent set) $$S^0\subseteq V$$ , and a non-negative integer k, the objective of BD-MaxIS is to find an independent set $$S\subseteq V$$ such that $$|S^0\setminus S|\le k$$ and |S| is maximized. The original MaxIS is generally NP-hard, but, it can be solved in polynomial time for perfect graphs (and therefore, comparability, co-comparability, bipartite, chordal, and interval graphs). In this paper, we show that BD-MaxIS is NP-hard even if the input is restricted to bipartite graphs, and hence to comparability graphs. On the other hand, fortunately, BD-MaxIS on co-comparability, interval, convex bipartite, and chordal graphs can be solved in polynomial time. Finally, we study the computational complexity on very similar variants of the Minimum Vertex Cover and the Maximum Clique problems for graph subclasses.

Abstract We consider a graph orientation problem that can be viewed as a generalization of Minimum Graph Coloring. Our problem takes as input an undirected graph $$G = (V, E)$$ G = ( V , E ) in which every edge $$\{u, v\} \in E$$ { u , v } ∈ E has two (potentially different and not necessarily positive) weights representing the lengths of its two possible directions ( u , v ) and ( v , u ), and asks for an orientation, i.e., an assignment of a direction to each edge of G , such that the length of a longest simple directed path in the resulting directed graph is minimized. A longest path in a graph is not always a maximal path when some edges have negative lengths, so the problem has two variants depending on whether all simple directed paths or maximal simple directed paths only are taken into account in the definition. We prove that the problems are NP-hard to approximate even if restricted to subcubic planar graphs, and develop fast polynomial-time algorithms for both problem variants for three classes of graphs: path graphs, cycle graphs, and star graphs.

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least $k$ vertices is considered long. When $k \le 3$, the problem is polynomial time solvable; when $k$ is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed $k \ge 4$, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a $k$-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when $k = 4$, the problem admits a $4$-approximation algorithm which was presented recently. We propose the first $(0.4394 k + O(1))$-approximation algorithm for the general problem and an improved $2$-approximation algorithm when $k = 4$. Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies.

In this paper, we study exact, exponential-time algorithms for a variant of the classic Longest Common Subsequence problem called the Repetition-Bounded Longest Common Subsequence problem (or RBLCS , for short): Let an alphabet S be a finite set of symbols and an occurrence constraint C o c c be a function C o c c : S → N , assigning an upper bound on the number of occurrences of each symbol in S . Given two sequences X and Y over the alphabet S and an occurrence constraint C o c c , the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s ∈ S appears at most C o c c ( s ) times in the obtained subsequence. The special case where C o c c ( s ) = 1 for every symbol s ∈ S is known as the Repetition-Free Longest Common Subsequence problem ( RFLCS ) and has been studied previously; e.g., in [1] , Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS . However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that | X | ≤ | Y | and | X | = n . In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O ( 1.44225 n ) . Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O ( 1.44225 n ) for any occurrence constraint C o c c , and even less in certain special cases. In particular, for RFLCS , our DP-based algorithm runs in O ( 1.41422 n ) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.

We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. This problem is closely related to the job scheduling on parallel machines, called the machine covering problem, where its goal is to assign jobs to parallel machines such that each machine is covered as much as possible. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 = ¿ for constant ¿ > 0 in polynomial time unless P = NP, even if all edge weights belong to {2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time wmax/wmin- approximation algorithm for MAXMINO where wmaxand wmindenote the maximum and minimum weights among all the input edges. Furthermore we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wminis at most logarithmic in the number of vertices. Finally, we, show that MAXMINO is solvable in polynomial time if the input is a cactus graph.

We present a deterministic, oblivious, permutation-routing algorithm on the n × n mesh of constant queue-size. It runs in (2.954+ε)n steps for any ε > 0. Previously, an O(n)-time algorithm was known but with no nontrivial upper bounds on the constant factor.