Back to research

IWOCA 2025 ยท Lecture Notes in Computer Science

A Space-Efficient Algorithm for Longest Common Almost Increasing Subsequence

A combinatorial algorithms paper by Md Tanzeem Rahat, Md. Manzurul Hasan, and Debajyoti Mondal, published at IWOCA 2025.

Problem

Given two number sequences and a positive threshold, find a longest common subsequence that is almost increasing. The problem blends LCS-style matching with a relaxed monotonicity constraint.

Why It Matters

LCaIS exposes a useful boundary between dense dynamic programming and structure-aware sequence algorithms, where matching pairs and compatibility relationships can be exploited.

Core Idea

The work reduces the memory burden of exact LCaIS computation and develops a match-sensitive algorithm that can be faster when the input is sparse in the right way.

Main Result

The paper gives an O(nmL)-time, O(n + mL)-space algorithm, and a second algorithm whose time depends on matching and compatible matching pairs.

What Was Difficult

The central difficulty is keeping enough state to recover the constrained common subsequence without carrying the full dense dynamic-programming table.

Open Directions

  • Can match-sensitive speedups be sharpened for practical sparse inputs?
  • Which related subsequence variants admit similar space reductions?
  • Can lower bounds clarify when dense dynamic programming is unavoidable?