I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music.

Problem Description

Given a section range in a song in seconds (or samples) , e.g. [10,20], I can look up where this section is repeated. Then we end up with a set of repeating sections like: [[10,20], [40,50], [70,80]]. We call this a group. A group has a certain fitness given to it.

(As a sidenote, the fitness of a group is defined as a combination of the sum of similarity values and how much of the song they cover alltogether)

Our goal is to find a set of disjoint groups that altogether have the highest fitness; the optimal decomposition of the repetitions. Below are two different valid decompositions of the same song, one course, and one fine decomposition.

Course decomposition

Fine decomposition

We are provided with a set of all candidate groups, here's a small selection, sorted top to bottom by fitness: Example of candidates

Current Greedy Method

  1. Sort all candidates by fitness
  2. Pick group G with the highest fitness
  3. Remove any groups from candidates if they have overlap with G
  4. Repeat from step 2 until no candidates are left


Sometimes the candidates overlap every so slightly, which in the context should perhaps not immediately lead to disqualification.

Example of slight overlap

There are options to relax the no-overlap rule. Note that each of the sections in a group has a different brightness. This brightness corresponds to a confidence, so in a group some sections are more certain to be proper repetitions than others.

For a group of sections G that we wish to add to a set of groups of sections S, we can:

  • simply remove sections from G if they overlap with any sections in S
  • trim the sides of to-be-added sections from G if they overlap with any sections in S
  • keep the overlapping sections in G

I hope this problem is interesting enough to you to give it a shot! Thank you!


1 Answer 1


If $n'$ is the number of groups, this problem admits no $2^{o(n')}$-time algorithm for any choice of a constant $\epsilon > 0$, unless the exponential time hypothesis (ETH) fails.

Let $G = (V, E)$ be an undirected graph with $n$ vertices $v_1, \dots, v_n$ and $m$ edges $e_1, \dots, e_m$.

Construct an instance of your problem by creating $n'=n$ groups as follows:

  • For each vertex $v_i \in V$, add a new group with fitness $1$ containing all intervals $[j-1, j]$ where $j$ is such that $v_i$ is an endpoint of $e_j$.

Any independent set $S \subseteq V$ of $G$ induces of collection of non-intersecting groups (except for the boundaries of the intervals) with total fitness $|S|$. On the converse, any subset of $S'$ non-intersecting groups must have total fitness $|S'|$ and induces an independent set of size $|S'|$ in $G$.

The claim follows since, assuming the ETH, there exists no $2^{o(n)}$-time algorithm for independent set.

Moreover, assuming $\mathsf{P} \neq \mathsf{NP}$, the above reduction also shows that for any constant $\epsilon>0$ there exists no polynomial-time $n^{1-\epsilon}$-approximation algorithm for your problem, even in the special case of unitary fitness. See, e.g., here.

  • 2
    $\begingroup$ In your construction, two groups intersect if there is a path of length 2 in $G$ between the two vertices. To fix this, you can associate vertex $v_i$ with a list $[j-1,j]$ for all edges $e_j$ incident to $i$. $\endgroup$ Jan 15, 2021 at 15:34
  • 1
    $\begingroup$ Thanks! I just added the interval $[i-1, i]$ in the group of $v_i$. This should fix it. $\endgroup$
    – Steven
    Jan 15, 2021 at 15:42
  • 2
    $\begingroup$ If $(i,j),(j,k) \in E$ then $[j-1,j]$ would appear both in the group of $v_i$ and in the group of $v_k$. $\endgroup$ Jan 15, 2021 at 15:44
  • $\begingroup$ D'oh! I see it now... thanks. $\endgroup$
    – Steven
    Jan 15, 2021 at 15:46
  • 1
    $\begingroup$ Sorry, the $0$ was a typo. It should be $1$. Yes, in my reduction each interval is shared by exactly 2 groups. If each group is a set of integers noting changes: just le the group of $v_i$ be $\{j : v \mbox{ is an endpoint of } e_j\}$. $\endgroup$
    – Steven
    Jan 15, 2021 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.