How to Attack the NP-complete Dag Realization Problem in Practice

Details How to Attack the NP-complete Dag Realization Problem in Practice How to Attack the NP-complete Dag Realization Problem in Practice

2012-03-16

arxiv.org/abs/1203.3636v1

Computer Science

Data Structures and Algorithms

20 pages, 11 figures, extended abstract to appear in Proceedings of SEA 2012

Scientific paper

We study the following fundamental realization problem of directed acyclic graphs (dags). Given a sequence S:=(a_1,b_1),...,(a_n, b_n) with a_i, b_i in Z_0^+, does there exist a dag (no parallel arcs allowed) with labeled vertex set V:= {v_1,...,v_n} such that for all v_i in V indegree and outdegree of v_i match exactly the given numbers a_i and b_i, respectively? Recently this decision problem has been shown to be NP-complete by Nichterlein (2011). However, we can show that several important classes of sequences are efficiently solvable. In previous work (Berger and Mueller-Hannemann, FCT2011), we have proved that yes-instances always have a special kind of topological order which allows us to reduce the number of possible topological orderings in most cases drastically. This leads to an exact exponential-time algorithm which significantly improves upon a straightforward approach. Moreover, a combination of this exponential-time algorithm with a special strategy gives a linear-time algorithm. Interestingly, in systematic experiments we observed that we could solve a huge majority of all instances by the linear-time heuristic. This motivates us to develop characteristics like dag density and "distance to provably easy sequences" which can give us an indicator how easy or difficult a given sequence can be realized. Furthermore, we propose a randomized algorithm which exploits our structural insight on topological sortings and uses a number of reduction rules. We observe that it clearly outperforms all other variants and behaves surprisingly well for almost all instances. Another striking observation is that our simple linear-time algorithm solves a set of real-world instances from different domains, namely ordered binary decision diagrams (OBDDs), train and flight schedules, as well as instances derived from food-web networks without any exception.

Affiliated with

Also associated with

No associations

Rating

How to Attack the NP-complete Dag Realization Problem in Practice does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How to Attack the NP-complete Dag Realization Problem in Practice, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How to Attack the NP-complete Dag Realization Problem in Practice will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-349476