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.

We introduce, as an enhancement of self-stabilization, the concept of monotonic self-stabilization for distributed systems that ensures that a certain measure of quality of state monotonically improves when the system in an illegitimate state progresses toward a legitimate state. In the concept, the quality is measured by a real-valued function that can be chosen from a certain class of functions. The concept is applied to a multi-robot pattern formation problem in which a group of autonomous mobile robots move from their respective initial positions to the goal positions like a marching band. We solve the problem by presenting two monotonic self-stabilizing pattern formation algorithms, one of which is for FSYNC model and the other is for SSYNC model. The considered real-valued functions to measure the quality take into account both the distance to the goal location and the accuracy of the formation. We present a formal proof of the algorithms' correctness and monotonic self-stability.

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 consider the problem of transporting a long object, such as a ladder, through a 90 degree corner in a corridor using two omnidirectional robots that do not necessarily have identical characteristics. A distributed algorithm is presented in which each robot computes its own motion based on the current and goal positions of the ladder, the locations of the walls, and the motion of the other robot observed indirectly through the link between the robot and the ladder. We evaluate the performance and robustness of the algorithm using extensive computer simulation by changing several parameter values that affect the key characteristics of the robots, including the maximum speed, the guide path through a corner, and the sensitivity and reaction to the motion of the other robot. The simulation results indicate that if the parameter values are chosen within certain reasonable ranges, then overall the algorithm works quite well even for robots having difficult characteristics. It is also shown that the robustness of the algorithm critically depends on the differences between the robots in the values of two parameters.