File Reductions.h

↰ Parent directory (ADS/complexity)

The polynomial reductions of chapter 18: a function f from the inputs of A to the inputs of B, computable in polynomial time, such that x is a YES of A if and only if f( x ) is a YES of B; then A is no harder than B (A :math:` propto ` B).

Definition (ADS/complexity/Reductions.h)

Detailed Description

  • DOMINO LIMITATO to CRICCA (Teorema 18.2): a node u_hij for the tile h in the square ( i , j ), only u_000 in ( 0 , 0 ), joined to the nodes of the squares not adjacent and to those of the adjacent squares whose tile fits, and k = n^2;

  • DOMINO LIMITATO to SODDISFATTIBILITA’ (Teorema 18.3): u_000, a tile at least and one at most in each square, and no two tiles that do not fit side by side;

  • DOMINO LIMITATO to PROGRAMMAZIONE LINEARE 0/1 (Teorema 18.4): x_000 = 1, one tile per square, and x_hij plus the tiles that do not fit next to it at most 1 (the example of the text writes one inequality per pair, which is the same since a square holds one tile);

  • CRICCA to INSIEME INDIPENDENTE (Teorema 18.5), the complement graph; INSIEME INDIPENDENTE to COPERTURA CON NODI (exercise 18.11), the complement of a set is a cover, k’ = n - k;

  • CIRCUITO HAMILTONIANO to COMMESSO VIAGGIATORE (Teorema 18.6): the distance 1 on the edges and 2 elsewhere, k = n;

  • PARTIZIONE to SCHEDULING MULTIPROCESSORE, SOMMA DI SOTTOINSIEME and ZAINO (Teoremi 18.7-18.9), half of the sum as the bound;

  • CIRCUITO HAMILTONIANO to CICLO HAMILTONIANO (exercise 18.12), both the orientations of each edge; CICLO HAMILTONIANO to CAMMINO HAMILTONIANO (exercise 18.13), the node 0 split into a start with its edges out and an end with its edges in; CICLO HAMILTONIANO to CATENA HAMILTONIANA (exercise 18.14), that path with each node made a chain of three and a pendant node at each end;

  • CAMMINO HAMILTONIANO from r to t to CAMMINO MASSIMO, k = n - 1, and CATENA HAMILTONIANA to ALBERO DI COPERTURA LIMITATO, k = 2 (exercises 18.15 and 18.16);

  • ORDINAMENTO to INVILUPPO CONVESSO: the points ( a_i , a_i^2 ) on the parabola are all vertices of the hull, in the order of the a_i, so the hull costs :math:` Omega( n log n ) `.

The contracts [see File Contract.h]: each reduction checks that its input is an instance of the problem reduced (a square or unoriented graph, a nonempty set of tiles, numbers not negative) and that its output has the shape of an instance of the target problem. The operations are defined in Reductions.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 18.5 and 18.7, https://algoritmicamente.it/materiali/libro/capitoli/cap18.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions