Consecutive Ones Property and PQ-Trees for Multisets: Hardness of Counting Their Orderings

Details Consecutive Ones Property and PQ-Trees for Multisets: Hardness of Counting Their Orderings Consecutive Ones Property and PQ-Trees for Multisets: Hardness of Counting Their Orderings

2011-01-31

arxiv.org/abs/1102.0041v2

Computer Science

Data Structures and Algorithms

Scientific paper

A binary matrix satisfies the consecutive ones property (COP) if its columns can be permuted such that the ones in each row of the resulting matrix are consecutive. Equivalently, a family of sets F = {Q_1,..,Q_m}, where Q_i is subset of R for some universe R, satisfies the COP if the symbols in R can be permuted such that the elements of each set Q_i occur consecutively, as a contiguous segment of the permutation of R's symbols. We consider the COP version on multisets and prove that counting its solutions is difficult (#P-complete). We prove completeness results also for counting the frontiers of PQ-trees, which are typically used for testing the COP on sets, thus showing that a polynomial algorithm is unlikely to exist when dealing with multisets. We use a combinatorial approach based on parsimonious reductions from the Hamiltonian path problem, showing that the decisional version of our problems is therefore NP-complete.

Affiliated with

Also associated with

No associations

Rating

Consecutive Ones Property and PQ-Trees for Multisets: Hardness of Counting Their Orderings 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 Consecutive Ones Property and PQ-Trees for Multisets: Hardness of Counting Their Orderings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Consecutive Ones Property and PQ-Trees for Multisets: Hardness of Counting Their Orderings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-499840