\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Integer Numbers
Undirected Graphs
Needed by:
Sheet PDF
Graph PDF

Decision Problems


A decision problem is a pair $(I, Y)$ of instances $I$ and yes-instances $Y \subset I$.


Subgraph isomorphism

Let $\mathcal{G} (n)$ be the set of graphs with $n$ vertices. For $m \leq n$, define $I = \mathcal{G} (n) \times \mathcal{G} (m)$. A graph $G_1 = (V_1, E_1)$ is subgraph-isomorphic to a graph $G_2 = (V_2, E_2)$ if there exists $V' \subset V_1$, $E' \subset E_1$ with $\num{V'} = \num{V_2}$, $\num{E'} = \num{E_2}$, and bijection $f: V' \to V_1$ so that

\[ \set{u, v} \in E_2 \iff \set{f(u), f(v)} \in E'. \]


\[ Y = \Set{(G_1, G_2) \in I}{G_1 \text{ is subgraph-isomorphic to } G_2} \]

We call $(Y, I)$ the subgraph-isomorphism problem.

Traveling Salesman

Denote by $S^n \subset \Z ^{n \times n}$ the set of symmetric integer-valued matrices. Define $I = S^n \times \Z $. A $n$-tour is a numbering $\pi : \set{1, \dots , n} \to \set{1, \dots , n}$ and has cost $C(\pi )$ with respect to $D$ defined by

\[ \textstyle C(\pi ) = D_{\pi (n), \pi (1)} + \sum_{j = 1}^{n-1} D_{\pi (i), \pi (i+1)} \]

A tour is $B$-bounded if its cost is no greater than $B$. Define $Y = \Set{(D,B)}{\text{ there is a }B-\text{bounded tour with respect to } D}$.

Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view