File Problems.h

↰ Parent directory (ADS/complexity)

The problems in NP of chapter 18, each with its polynomial certificate, which checks a proposed solution, and an enumeration by backtrack, which decides the problem in exponential time and returns a solution if there is one.

Definition (ADS/complexity/Problems.h)

Detailed Description

The graphs are adjacency matrices, symmetric when unoriented, whose diagonal (a loop of a node) every problem ignores: a node with a loop may be in an independent set, need not be in a cover and takes a color like any other; the formulas in conjunctive normal form are clauses of literals, +( v + 1 ) for the variable v and -( v + 1 ) for its negation; a system of 0/1 linear programming is A x <= b.

  • clique() (CRICCA, enCricca()), independentSet(), vertexCover(), coloring() (exercise 18.6), bisection();

  • tsp() (COMMESSO VIAGGIATORE, enTsp(), pruned when the partial length exceeds k), hamiltonianCircuit() (unoriented), hamiltonianCycle() and hamiltonianPath() (oriented, exercises 18.12 and 18.13), hamiltonianChain() (unoriented, exercise 18.14), longestPath() and longestPathDag(), polynomial on an acyclic graph (exercise 18.15), boundedSpanningTree() (exercise 18.16);

  • satisfiable() (SODDISFATTIBILITA’), lp01() (PROGRAMMAZIONE LINEARE 0/1);

  • partition(), subsetSumExists(), knapsackDecision() (ZAINO, exercise 18.5), multiprocessorScheduling(), exactCover3() (exercise 18.7), threeDimensionalMatching(), bribes() (exercises 18.1 and 18.4).

The contracts [see File Contract.h]: the graphs are square adjacency matrices, unoriented (symmetric) where the problem is, the literals name the variables of the formula, the numbers of the numerical problems are not negative; each certificate returned by an enumeration is checked as a postcondition. The operations are defined in Problems.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 18, https://algoritmicamente.it/materiali/libro/capitoli/cap18.pdf

    1. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, 85-103, 1972, doi:10.1007/978-1-4684-2001-2_9

    1. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions

Typedefs