Is this NP-complete?

Thread View: comp.theory

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by Brendan McKay Sun, 10 Jan 1993 15:48

#1933

Author: Brendan McKay
Date: Sun, 10 Jan 1993 15:48

17 lines
1164 bytes

A generalised regular family (GRF) of sets is represented by a 
vector (bot;top[1],...,top[n]) where bot and each top[i] are sets, 
and each top[i] is a superset of bot.  The GRF consists of all  
sets X such that bot <= X <= top[i] for some i, where "<=" means 
"subset".  A _simple_ GRF is one with n=1.

INSTANCE:  A GRF F; and integer K >= 0.
QUESTION:  Is F equal to the disjoint union of at most K
           simple GRFs?

What is the complexity of this problem?  I suspect it is NP-complete
but can't rule out some simple dynamic program (or something).
This problem arose from a graph computation that runs faster
if GRFs can be quickly split into a small number of simple GRFs.

Thanks,
Brendan McKay.

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads