Collection of subsets such that each element of the original set is contained in exactly one subset
In the mathematical field of combinatorics, given a collection of subsets of a set , an exact cover is a subcollection of such that each element in is contained in exactly one subset in .
One says that each element in is covered by exactly one subset in .[1]
An exact cover is a kind of cover. It is non-deterministic polynomial time (NP) complete and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design.[2]
In other words, is a partition of consisting of subsets contained in .
The exact cover problem to find an exact cover is a kind of constraint satisfaction problem. The elements of represent choices and the elements of represent constraints.
An exact cover problem involves the relation contains between subsets and elements. But an exact cover problem can be represented by any heterogeneous relation between a set of choices and a set of constraints. For example, an exact cover problem is equivalent to an exact hitting set problem, an incidence matrix, or a bipartite graph.
In computer science, the exact cover problem is a decision problem to determine if an exact cover exists. The exact cover problem is NP-complete[3] and is one of Karp's 21 NP-complete problems.[4] It is NP-complete even when each subset in S contains exactly three elements; this restricted problem is known as exact cover by 3-sets, often abbreviated X3C.[3]
Knuth's Algorithm X is an algorithm that finds all solutions to an exact cover problem. DLX is the name given to Algorithm X when it is implemented efficiently using Donald Knuth's Dancing Links technique on a computer.[5]
The exact cover problem can be generalized slightly to involve not only exactly-once constraints but also at-most-once constraints.
Finding Pentomino tilings and solving Sudoku are noteworthy examples of exact cover problems. The n queens problem is a generalized exact cover problem.
^Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation
Pradheebha Surendiran, Christoph Robert Meinecke, Aseem Salhotra, Georg Heldt, Jingyuan Zhu, Alf Månsson, Stefan Diez, Danny Reuter, Hillel Kugler, Heiner Linke, and Till Korten
2022 2 (5), 396-403
DOI: 10.1021/acsnanoscienceau.2c00013
^Korten, Till; Diez, Stefan; Linke, Heiner; Nicolau, Dan V; Kugler, Hillel (2021-08-01). "Design of network-based biocomputation circuits for the exact cover problem". New Journal of Physics. 23 (8): 085004. doi:10.1088/1367-2630/ac175d. ISSN 1367-2630.
^ ab
M.R. Garey; D.S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
^Richard M. Karp (1972). "Reducibility among combinatorial problems" (PDF). In R.E. Miller; J.W. Thatcher (eds.). Complexity of Computer Computations. Proc. of a Symp. on the Complexity of Computer Computations. New York: Plenum. pp. 85–103. ISBN 0-3063-0707-3. Archived from the original (PDF) on 2011-06-29. Retrieved 2008-06-27.
^Cite error: The named reference knuth was invoked but never defined (see the help page).
{\displaystyle {\mathcal {S}}} of subsets of a set X {\displaystyle X} , an exactcover is a subcollection S ∗ {\displaystyle {\mathcal {S}}^{*}} of S {\displaystyle...
all sudokus. Sudoku puzzles may be described as an exactcover problem, or more precisely, an exact hitting set problem. This allows for an elegant description...
from Set cover. Exactcover problem is to choose a set cover with no element included in more than one covering set. Red-blue set cover. Set-cover abduction...
the exactcover problem. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exactcover problem...
that no two instances of the same digit are in the same row or column. Exactcover Consider a matrix with one primary column for each of the n ranks of...
Exact Audio Copy (EAC) is a CD ripping program for Microsoft Windows. The program has been developed by Andre Wiethoff since 1998. Wiethoff's motivation...
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph...
developed by XMOS Capacitive reactance or XC, a property of a capacitor Exactcover problem, in theoretical computer science Xeno-canto, citizen science...
\choose n}.} Wikimedia Commons has media related to Set partitions. Exactcover Block design Cluster analysis List of partition topics Lamination (topology)...
an exactcover is an NP-complete problem, even in the special case in which the size of all sets is 3 (this special case is called exact 3 cover or X3C)...
sequence § Spectral Sequence of an exact couple. For a basic example, see Bockstein spectral sequence. The present article covers additional materials. Let R...
forest cover in India by state. Tree density is the quantification of how closely the trees are growing in a hectare area. It is not the exact number...
Cover your ass (British: cover your arse), abbreviated CYA, is an activity done by individuals to protect themselves from possible subsequent criticism...
densiometer, and hemispherical photography. Exactcover measurements should be made in vertical direction, or the cover percent will be overestimated. Aerial...
the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. This is sometimes known as exact vertex...
to CW complexes. Suppose that B is path-connected. Then there is a long exact sequence of homotopy groups ⋯ → π n ( F ) → π n ( E ) → π n ( B ) → π n...
astronauts, Al Bishop (the "Bishop Covers"). Especially in the case of the MSCSC Covers, there are many of the exactcovers that the stamp collectors also...
"Duck and cover" is a method of personal protection against the effects of a nuclear explosion. Ducking and covering is useful in offering a degree of...
extent to which a locally exact sequence on a fixed topological space, for instance the de Rham sequence, fails to be globally exact. Its definition, using...
over R with M preserves exact sequences. A module is faithfully flat if taking the tensor product with a sequence produces an exact sequence if and only...
for their 2006 album Specification.Fifteen. Deupree called U2's cover "nearly an exact rip-off" and stated that for the band to obtain the rights to the...
A cover meter is an instrument to locate rebars and measure the exact concrete cover. Rebar detectors are less sophisticated devices that can only locate...
underlying manifold is the double cover of the special orthogonal group SO(n) = SO(n, R), such that there exists a short exact sequence of Lie groups (when...
Global Information
