# Is this graph problem NP-Hard?

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.

• There is a natural local search or MCMC you can try as a practical approach, although as Bullet51s answer shows it won't always succeed. The states of the chain are your set of $K$ nodes. A move of the Markov chain (or local search) is to randomly update the position of one of the nodes using your objective function. However, since clique is a special case, and clique is hard to approximate you'll need to impose more structure on the graph to prove an approximation bound. Can you solve the problem on trees / bounded treewidth? Anyhow, maybe worth coding and trying MCMC optimization heuristics. – Lorenzo Najt Oct 3 '19 at 13:46
• You may have more luck here: cstheory.stackexchange.com or here: or.stackexchange.com – Lorenzo Najt Oct 3 '19 at 13:46

The problem is at least as hard as the 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$$.

• Is the clique problem NP-hard? – dineshdileep Oct 3 '19 at 23:51
• The problem of finding a clique is NP-hard. – LeechLattice Oct 4 '19 at 4:38
• so can we conclude that a specific instance of my problem is NP-Hard and so the problem itself is? – dineshdileep Oct 4 '19 at 7:58
• also, Please note that graph in question is a fully connected graph. Thus any $K$ subset is a clique. Does that change anything – dineshdileep Oct 4 '19 at 8:05
• The clique problem in $G'$ corresponds to finding a subgraph in $A$ with all edges weighted $1$. – LeechLattice Oct 4 '19 at 8:16