I had asked this question in [math.se](https://math.stackexchange.com/questions/3375396/is-this-graph-problem-np-hard?noredirect=1#comment6946013_3375396) without any success


Let $A$ be the symmetric $n\times n$ adjacency matrix for a graph where $A\_{ij}$ is the positive edge value between node $i$ and $j$ (thus fully connected graph). Among the $n-$ nodes, let $c$ be a given node of interest (called a central node in my problem). Define the matrix
\begin{align}
B\_{ij}=\begin{cases} 0 &,~~i=j \\ \frac{A\_{ij}}{A\_{ic}A\_{jc}} &,~~\text{otherwise}
\end{cases}
\end{align}
Thus the individual elements are proportional to distance between $i$ and $j$ and inversely proportional to distance from the central node. Thus, this term will be high for pairs which are close to central node, but far from each other.
I am interested in solving the following optimization problem
\begin{align}
\max\_{x\_{ij}}\sum\_{i,j}x\_ix\_j&B\_{ij} 
\\s.t.~~\sum\_{i=1}^{n}x\_i\leq K ~~,&~~x\_i\in\{0,1\}
\end{align}
Intuitively, I need to select $K$ nodes such that they are as close as possible to the central node yet far apart among themselves?


Is this problem studied in literature? Is it NP-Hard? what are the known practical approaches? I am familiar with the Semidefinite formulation of this. I am interested in knowing if there are graph based approaches.



Is this graph problem NP-Hard?
The problem is at least as hard as the [clique problem](https://en.wikipedia.org/wiki/Clique_problem): Take a graph $G$. Let $G'$ be a new graph with vertices $V(G)+c$ and edges $E(G)+\{(g,c)|g\in V(G)\}$. 


Let $A\_{ij}=1$ if $ij$ is an edge in $G'$, and $0.5$ otherwise. As $A\_{ic}=1$ for all vertices $i$, we have 


\begin{align}
B\_{ij}=\begin{cases} 0 &,~~i=j \\ A\_{ij} &,~~\text{otherwise}
\end{cases}
\end{align}


Finding a solution of $K(K-1)$ to your maximizing problem is equivalent to finding a $K$-clique in the graph $G'$, which corresponds to a $(K-1)$-clique in $G$.


