I have a digraph D on n vertices formed in the following manner:

  • I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more than once in a given list.
  • I create a node for each integer, with an arc from node x to y if x appears before y in at least one list.

How can I find a maximum set of nodes that induce a DAG?

Assuming that's an NP-hard problem (as per this paper: https://osf.io/c3gmu), is there a more efficient approach to get a near-maximal induced DAG?

--- update ---

Here's a possible approach for an approximate solution.

  • create a set S of all elements (integers 1-n)
  • create two sets for each integer. One containing the set of integers to the left of the integer in any list, and the other containing the set of integers to the right of the integer in any list. For integer t, call these L(t) and R(t) for left & right respectively.

Now we can generate a random induced DAG as follows. Let D be the set of vertices in the DAG, initially empty, L(D) the set of vertices to the left of some element of D in some list, R(D) the set to the right.

  1. Move a random vertex v from S to D.
  2. Update L(D) & R(D): L(D) = L(D) U L(v), R(D) = R(D) U R(v)
  3. Remove the intersection of L(D) and R(D) from S.
  4. Repeat as long as |S| > 0

That gets us a random maximal DAG. We can repeat it many times and keep track of the largest to get a large random maximal DAG. To save time, instead of actually modifying S, we can keep track of the set B of 'banned elements' or elements that would be removed from S in this algorithm.

Thoughts on this approach?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.