494:: This technique improves on backtracking by exploring the space of all possible solutions but solving at each step the problem of whether the current partial solution can be extended to a partial solution. If the answer is no, then the algorithm can immediately backtrack and avoid wasting time, which makes it easier to show guarantees on the delay between any two complete solutions. In particular, this technique applies well to
40:. For each input, the enumeration algorithm must produce the list of all solutions, without duplicates, and then halt. The performance of an enumeration algorithm is measured in terms of the time required to produce the solutions, either in terms of the
697:
problems. This is the class of sets for which there exist an enumeration algorithm that will produce all elements of the set: the algorithm may run forever if the set is infinite, but each solution must be produced by the algorithm after a finite time.
512:, then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a
52:
time, counted as the time before outputting the first solution. This complexity can be expressed in terms of the size of the input, the size of each individual output, or the total size of the set of all outputs, similarly to what is done with
483:
it at each successive step). However, performing this may not give good guarantees on the delay, i.e., a backtracking algorithm may spend a long time exploring parts of the space of possible results that do not give rise to a full
458:, the class of problems where the delay before each output is polynomial in the size of this specific output (and independent from the input or from the other outputs). The preprocessing is generally assumed to be polynomial.
178:
464:, the class of problems where the delay before each output is constant, i.e., independent from the input and output. The preprocessing phase is generally assumed to be polynomial in the input.
813:
Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne (2007). Duparc, Jacques; Henzinger, Thomas A. (eds.). "On
Acyclic Conjunctive Queries and Constant Delay Enumeration".
324:
130:
286:
508:
of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in
344:
260:
240:
220:
200:
103:
83:
554:
520:
of two sets can be enumerated efficiently by enumerating one set and joining each result with all results obtained when enumerating the second step.
452:, the class of problems where the delay between two consecutive outputs is polynomial in the input (and independent from the output).
373:
in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input
137:
834:
797:
36:. Formally, such an algorithm applies to problems that take an input and produce a list of solutions, similarly to
355:
639:
624:
479:: The simplest way to enumerate all solutions is by systematically exploring the space of possible results (
604:
608:
110:
531:
54:
415:
Other classes that have been defined include the following. In the case of problems that are also in
406:
106:
558:
655:
651:
647:
480:
291:
756:
694:
667:
402:
115:
33:
265:
684:
671:
585:
562:
8:
900:
628:
539:
369:, the class of problems for which the correctness of a possible output can be checked in
877:
859:
632:
505:
329:
245:
225:
205:
185:
88:
68:
830:
793:
581:
547:
543:
517:
37:
881:
869:
822:
768:
730:
643:
448:
382:
359:
17:
440:-th output can be produced in polynomial time in the input size and in the number
826:
787:
689:
663:
589:
566:
426:, the class of problems whose complete output can be computed in polynomial time.
409:
370:
401:. For instance, this class contains all problems that amount to enumerating the
748:
577:
495:
757:"Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees"
894:
772:
752:
597:
734:
570:
475:
593:
29:
513:
873:
718:
25:
719:"Efficient Enumeration of Solutions Produced by Closure Operations"
618:
535:
864:
683:
The notion of enumeration algorithms is also used in the field of
850:
Marquis, P.; Darwiche, A. (2002). "A Knowledge
Compilation Map".
614:
509:
44:
required to produce all solutions, or in terms of the maximal
659:
419:, these problems are ordered from least to most specific:
354:
Enumeration problems have been studied in the context of
789:
222:
the algorithm produces the (possibly infinite) sequence
173:{\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}
723:
592:
of which conjunctive queries could be enumerated with
678:
332:
294:
268:
248:
228:
208:
188:
140:
118:
91:
71:
812:
48:
between two consecutive solutions and in terms of a
524:
338:
318:
280:
254:
234:
214:
194:
172:
124:
97:
77:
892:
849:
687:to define some high complexity classes such as
623:Several problems on graphs, e.g., enumerating
716:
349:
326:. The algorithm should halt if the sequence
852:Journal of Artificial Intelligence Research
613:Listing all elements of structures such as
747:
863:
712:
710:
565:and is connected to many applications in
362:have been introduced for such problems.
821:. Springer Berlin Heidelberg: 208–222.
588:. There have been characterizations in
504:: If we wish to enumerate the disjoint
432:, the class of problems where, for all
893:
717:Strozecki, Yann; Mary, Arnaud (2019).
707:
817:. Lecture Notes in Computer Science.
785:
646:, e.g., a Boolean formula written in
60:
468:
13:
679:Connection to computability theory
607:in an input graph, e.g., with the
389:is a correct output for the input
161:
148:
119:
14:
912:
666:in restricted classes studied in
525:Examples of enumeration problems
356:computational complexity theory
843:
806:
779:
741:
307:
295:
1:
701:
576:Enumerating the answers to a
561:. This problem is related to
365:A very general such class is
827:10.1007/978-3-540-74915-8_18
502:Closure under set operations
7:
605:enumerating maximal cliques
430:Incremental polynomial time
55:output-sensitive algorithms
10:
917:
546:and we must enumerate the
532:vertex enumeration problem
319:{\displaystyle (x,z)\in R}
456:Strongly polynomial delay
350:Common complexity classes
85:is defined as a relation
792:. Göttingen: Cuvillier.
786:Hagen, Matthias (2008).
773:10.1002/net.1975.5.3.237
584:or a query expressed in
393:, in polynomial time in
656:binary decision diagram
652:disjunctive normal form
648:conjunctive normal form
609:Bron–Kerbosch algorithm
534:, where we are given a
377:, the candidate output
125:{\displaystyle \Sigma }
65:An enumeration problem
815:Computer Science Logic
735:10.23638/DMTCS-21-3-22
695:recursively enumerable
642:of representations of
640:satisfying assignments
340:
320:
282:
281:{\displaystyle z\in y}
256:
236:
216:
196:
174:
126:
99:
79:
668:knowledge compilation
341:
321:
283:
262:has no duplicate and
257:
237:
217:
197:
175:
127:
100:
80:
34:computational problem
22:enumeration algorithm
685:computability theory
586:monadic second-order
563:monotone dualization
555:minimal transversals
405:of a problem in the
330:
292:
266:
246:
226:
206:
186:
182:An algorithm solves
138:
116:
89:
69:
693:, the class of all
544:linear inequalities
202:if for every input
596:preprocessing and
360:complexity classes
336:
316:
278:
252:
232:
212:
192:
170:
122:
95:
75:
61:Formal definitions
753:Tarjan, Robert E.
644:Boolean functions
582:conjunctive query
580:, for instance a
518:cartesian product
490:Flashlight search
469:Common techniques
424:Output polynomial
381:, and solves the
339:{\displaystyle y}
255:{\displaystyle y}
235:{\displaystyle y}
215:{\displaystyle x}
195:{\displaystyle P}
98:{\displaystyle R}
78:{\displaystyle P}
38:function problems
32:the answers to a
908:
886:
885:
874:10.1613/jair.989
867:
847:
841:
840:
810:
804:
803:
783:
777:
776:
745:
739:
738:
714:
638:Enumerating the
625:independent sets
553:Enumerating the
550:of the polytope.
516:. Likewise, the
492:
491:
449:Polynomial delay
383:decision problem
345:
343:
342:
337:
325:
323:
322:
317:
287:
285:
284:
279:
261:
259:
258:
253:
241:
239:
238:
233:
221:
219:
218:
213:
201:
199:
198:
193:
179:
177:
176:
171:
169:
168:
156:
155:
131:
129:
128:
123:
109:of an arbitrary
104:
102:
101:
96:
84:
82:
81:
76:
18:computer science
916:
915:
911:
910:
909:
907:
906:
905:
891:
890:
889:
848:
844:
837:
811:
807:
800:
784:
780:
749:Read, Ronald C.
746:
742:
715:
708:
704:
681:
664:Boolean circuit
603:The problem of
590:database theory
567:database theory
538:described as a
527:
489:
488:
471:
371:polynomial time
352:
331:
328:
327:
293:
290:
289:
288:if and only if
267:
264:
263:
247:
244:
243:
227:
224:
223:
207:
204:
203:
187:
184:
183:
164:
160:
151:
147:
139:
136:
135:
117:
114:
113:
90:
87:
86:
70:
67:
66:
63:
12:
11:
5:
914:
904:
903:
888:
887:
842:
835:
805:
798:
778:
767:(3): 237–252.
740:
705:
703:
700:
680:
677:
676:
675:
636:
621:
611:
601:
578:database query
574:
551:
526:
523:
522:
521:
499:
496:self-reducible
485:
470:
467:
466:
465:
462:Constant delay
459:
453:
445:
427:
358:, and several
351:
348:
335:
315:
312:
309:
306:
303:
300:
297:
277:
274:
271:
251:
231:
211:
191:
167:
163:
159:
154:
150:
146:
143:
121:
94:
74:
62:
59:
9:
6:
4:
3:
2:
913:
902:
899:
898:
896:
883:
879:
875:
871:
866:
861:
857:
853:
846:
838:
836:9783540749158
832:
828:
824:
820:
816:
809:
801:
799:9783736928268
795:
791:
790:
782:
774:
770:
766:
762:
758:
754:
750:
744:
736:
732:
728:
724:
720:
713:
711:
706:
699:
696:
692:
691:
686:
673:
669:
665:
661:
657:
653:
649:
645:
641:
637:
634:
630:
626:
622:
620:
616:
612:
610:
606:
602:
599:
595:
591:
587:
583:
579:
575:
572:
568:
564:
560:
556:
552:
549:
545:
541:
537:
533:
529:
528:
519:
515:
511:
507:
503:
500:
497:
493:
486:
482:
478:
477:
473:
472:
463:
460:
457:
454:
451:
450:
446:
443:
439:
435:
431:
428:
425:
422:
421:
420:
418:
413:
411:
408:
404:
400:
396:
392:
388:
384:
380:
376:
372:
368:
363:
361:
357:
347:
333:
313:
310:
304:
301:
298:
275:
272:
269:
249:
229:
209:
189:
180:
165:
157:
152:
144:
141:
133:
112:
108:
92:
72:
58:
56:
51:
50:preprocessing
47:
43:
39:
35:
31:
27:
23:
19:
855:
851:
845:
818:
814:
808:
788:
781:
764:
760:
743:
726:
722:
688:
682:
571:graph theory
510:sorted order
501:
487:
481:partitioning
476:Backtracking
474:
461:
455:
447:
441:
437:
433:
429:
423:
416:
414:
398:
394:
390:
386:
378:
374:
366:
364:
353:
181:
134:
64:
49:
45:
41:
21:
15:
858:: 229–264.
658:such as an
385:of whether
346:is finite.
901:Algorithms
702:References
559:hypergraph
514:hash table
242:such that
42:total time
30:enumerates
865:1106.1819
619:greedoids
498:problems.
484:solution.
403:witnesses
311:∈
273:∈
166:∗
162:Σ
158:×
153:∗
149:Σ
145:⊆
120:Σ
26:algorithm
895:Category
761:Networks
755:(1975).
670:, e.g.,
615:matroids
598:constant
548:vertices
536:polytope
111:alphabet
882:9919794
662:, or a
107:strings
880:
833:
796:
635:, etc.
600:delay.
594:linear
540:system
436:, the
24:is an
878:S2CID
860:arXiv
729:(3).
629:paths
557:of a
506:union
417:EnumP
407:class
367:EnumP
105:over
46:delay
28:that
20:, an
831:ISBN
819:4646
794:ISBN
660:OBDD
654:, a
633:cuts
617:and
569:and
530:The
397:and
870:doi
823:doi
769:doi
731:doi
672:NNF
650:or
542:of
16:In
897::
876:.
868:.
856:17
854:.
829:.
763:.
759:.
751:;
727:21
725:.
721:.
709:^
690:RE
631:,
627:,
412:.
410:NP
132::
57:.
884:.
872::
862::
839:.
825::
802:.
775:.
771::
765:5
737:.
733::
674:.
573:.
444:.
442:i
438:i
434:i
399:y
395:x
391:x
387:y
379:y
375:x
334:y
314:R
308:)
305:z
302:,
299:x
296:(
276:y
270:z
250:y
230:y
210:x
190:P
142:R
93:R
73:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.