I am working on the famous maximum independent set problem on a graph class called progressive $k$-partite graph, and it is defined as follows.

Given a graph $G = (V_1, V_2, \dots, V_k, E)$, where $V_i\ |\ i \in \{1,2,\dots, k\}$ are the partitions and $E$ is the edge set. We assume that the vertices of each partition is ordered. The order of the vertices in each partition is determined by a function $f: \mathbb{N} \rightarrow \mathbb{N}$, which takes a vertex as the parameter, and returns the order of that vertex in its partition.

The progressive rule is, if a vertex $v$ in some partition $V_i$ is adjacent to a vertex $u$ in another partition $V_j$, it must be also adjacent to vertices that have higher precedence, or lower precedence in $V_j$ w.r.t. the function $f$.

Moreover, there exists another function $g(V_i,V_j)$, that takes a pair of partitions as input, and outputs whether the progressive rule is applied forwards or backwards. If $g(i,j) = 0$, then an edge $uv$ from a vertex in $V_i$ to a vertex in $V_j$ means $u$ is also adjacent all $x$ vertices such that $f(x) < f(v)$. Otherwise, if $g(i,j) = 1$, then u is also adjacent to all $x$ vertices such that $f(x) > f(v)$.

To write formally,

$$ uv \in E \Leftrightarrow ux \in E\ \text{s.t. } u \in V_i, v,x \in V_j \begin{cases} f(u) < f(x), & \text{if} & g(i,j) = 0 \\ f(u) > f(x), & \text{if} & g(i,j) = 1 \end{cases} $$

also, $$ f(i,j) = 0 \Leftrightarrow f(j,i) = 1$$

So, basically, vertices are ordered in each partition, and for each pair of parititions, the progressive rule is dictated by another function.

You can interpret this scenario as a leveling system in a game. There are $k$ teams with arbitrary number of players in each, and each team hands in an ordered list of their players. To compete with a player in a partition, one must also compete all the players that are listed either below or above that player. The function $g$ determines, for each pair of teams, in which order they have to compete.

So, my question is,

Given $G, f, g$, is finding maximum independent set NP-hard?

I think it is not, because we can use a quadratic-time algorithm, which checks a local independent set for a pair, and iterates by adding other pairs that are connected to them. However, I don't have a concrete algorithm.

  • $\begingroup$ 1. "it must be also adjacent to vertices that have higher precedence, or lower precedence" - I'm confused. Which is it? It must be adjacent to vertices that have higher precedence? It must be adjacent to vertices that have lower precedence? It must be adjacent to both types of vertices? Right now the definition is unclear. 2. What does "higher precedence ... w.r.t. the function $f$" mean? Also you haven't even introduced the notion of a function $f$ yet. Please define/introduce all notation before first use. $\endgroup$ – D.W. Feb 4 '18 at 7:19
  • $\begingroup$ 3. In your equation after "To write formally", what is the meaning of the vertical bar ($\|$)? I'm not familiar with that notation. What is the meaning of the curly braces and stuff to the right of it? I don't understand the syntax/notation you are using here. $\endgroup$ – D.W. Feb 4 '18 at 7:21

Your Answer

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

Browse other questions tagged or ask your own question.