Liste de problèmes NP-complets - Définition

Introduction

Ceci est une liste des problèmes NP-complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d'un problèmes de la décision. Puisqu'on connaît plus de 3000 problèmes NP-complets, cette liste n'est pas exhaustive. La plupart des problèmes énumérés proviennent du livre fondamental de Garey et Johnson : Computers and Intractability: A Guide to the Theory of NP-Completeness . Ils sont présentés ici suivant les mêmes ordre et organisation.

Géométrie algorithmique

• Triangulation avec poids minimal d'un ensemble de points dans le plan
• Tester si un arbre peut être représenté comme un arbre couvrant minimum euclidien
• Reconnaissance d'un graphe d'un disque unitaire (c'est le graphe d'intersection du cercle unitaire dans le plan)
• Plusieurs problèmes de planification de mouvement au travers des obstacles polygonaux dans le plan sont NP-difficiles.
  • Partition planaire en sous-assemblements connectés : étant donné un ensemble A de polygones dans le plan qui peuvent se toucher mais ne se chevauchent pas, décider s'il y a un sous-ensemble non-trivial S de A qui peut être séparé de A\S par un déplacement rigide et sans collision de S et tel que S et A\S sont connectés.

Conception de réseau

Arbres couvrants

Degree constrained spanning tree · Maximum leaf spanning tree · Shortest total path length spanning tree · Bounded diameter spanning tree · Capacitated spanning tree · Geometric capacitated spanning tree · Optimum communication spanning tree · Isomorphic spanning tree · Kth best spanning tree · Bounded component spanning forest · Multiple choice branching · Arbre de Steiner · Geometric Steiner tree · Cable Trench Problem

Coupures et connexité

Graph partitioning · Acyclic partition · Max weight cut · Minimum cut into bounded sets · Biconnectivity augmentation · Strong connectivity augmentation · Network reliability · Network survivability · Multiway Cut · Minimum k-cut

Routage

Bottleneck traveling salesman · Chinese postman for mixed graphs · Euclidean traveling salesman · K most vital arcs · Kth shortest path · Metric traveling salesman · Longest circuit · Longest path · Prize Collecting Traveling Salesman · Rural Postman · Shortest path in general networks · Shortest weight-constrained path · Stacker-crane · Time constrained traveling salesman feasibility · Problème du voyageur de commerce · Problème de tournées de véhicules

Flux

Minimum edge-cost flow · Integral flow with multipliers · Path constrained network flow · Integral flow with homologous arcs · Integral flow with bundles · Undirected flow with lower bounds · Directed two-commodity integral flow · Undirected two-commodity integral flow · Disjoint connecting paths · Maximum length-bounded disjoint paths · Maximum fixed-length disjoint paths · Unsplittable multicommodity flow

Divers

Quadratic assignment problem · Minimizing dummy activities in PERT networks · Constrained triangulation · Intersection graph for segments on a grid · Edge embedding on a grid · Geometric connected dominating set · Minimum broadcast time · Min-max multicenter · Min-sum multicenter · Uncapacitated Facility Location · Metric k-center

Théorie des graphes

Couverture et découpage en partitions

Couverture des sommets · Ensemble dominant · Nombre domatique · Coloration de graphe à k couleurs · Nombre achromatique · Triangle monochromatique · Ensemble de sommets à rétroaction · Ensemble d'arcs à rétroaction · Ensembles de côtés à rétroaction partielle · Pairage maximal minimum · Partition en triangles · Partition en sous-graphes isomorphiques · Partition en sous-graphes hamiltoniens · Partition en forêts · Partition en cliques · Partition en pairages parfaits · Pairage stochastique de poids maximum en deux étapes · Couverture par cliques · Couverture par sous-graphes bipartis complets

Sous-graphes et super-graphes

. Clique maximum . Stable maximum · Ensemble indépendant · Induced subgraph with property Pi · Induced connected subgraph with property Pi · Induced path · Balanced complete bipartite subgraph · Bipartite subgraph · Degree-bounded connected subgraph · Planar subgraph · Edge-subgraph · Transitive subgraph · Uniconnected subgraph · Minimum k-connected subgraph · Cubic subgraph · Minimum equivalent digraph · Hamiltonian completion · Interval graph completion · Path graph completion

Tri des sommets

Cycle hamiltonien · Cycle hamiltonien orienté · Chemin Hamiltonien · Bandwidth · Directed bandwidth · Optimal linear arrangement · Directed optimal linear arrangement · Minimum cut linear arrangement · Rooted tree arrangement · Directed elimination ordering · Elimination degree sequence

Morphismes

Isomorphisme de sous-graphe · Plus grand sous-graphe commun · Maximum subgraph matching · Graph contractability · Digraph D-morphism

Divers

Path with forbidden pairs · Multiple choice matching · Graph Grundy numbering · Kernel · K-closure · Intersection graph basis · Path distinguishers · Metric dimension · Nesetril-Rödl dimension · Threshold number · Oriented diameter · Weighted diameter