Let $\mathfrak{G}$ be the class of all finite connected undirected graphs, $A,B \subseteq \mathfrak{G}$. Let $X[n]=\{G\in X :v(G)=n\}$, consider a function: $$KE_n(A,B)=\max_{G\in A[n]}\min_{G\subseteq H,H\in B}|H|$$ I would like to know for what $A,B$ is the function $KE_n(A,B)$ computable? Obviously, this is true if $A$ and $B$ (or even just $B$) are finite. This is also true for some pairs of simple classes like $(A,COM)$, where $COM$ is a class of complete graphs. Are there more general criteria for the computability of this function?
$\begingroup$
$\endgroup$
8
-
$\begingroup$ How is the set $B$ given? The $\text{max}$ part is just finite and does not affect computability. $\endgroup$– LeechLatticeCommented Feb 23, 2022 at 16:18
-
$\begingroup$ @LeechLattice , I need the machine to be able to recognize both $A$ and $B$. The fact that max does not affect computability is not entirely clear, because the machine needs to know which graphs from $A[n]$ it can take to test for the maximum. $\endgroup$– Ben TomCommented Feb 23, 2022 at 16:32
-
$\begingroup$ The machine can just enumerate all $n$-vertex graphs to find graphs that can play the role for $G$, and it can also enumerate graphs by increasing order of vertices to find which graph can play the role of $H$. $\endgroup$– LeechLatticeCommented Feb 23, 2022 at 16:39
-
$\begingroup$ @LeechLattice , what if for any $G \in A[n]$ there is no $H \in B$ such that $G$ embeds in $H$? How does the machine know when to stop? $\endgroup$– Ben TomCommented Feb 23, 2022 at 16:48
-
$\begingroup$ This is not even a total function. For example, what if $A[n]$ is empty for some $n$? $\endgroup$– 喻 良Commented Feb 25, 2022 at 11:15
|
Show 3 more comments