2
$\begingroup$

I had asked this question in math.se 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Lorenzo Najt Oct 3 '19 at 13:46
  • 1
    $\begingroup$ You may have more luck here: cstheory.stackexchange.com or here: or.stackexchange.com $\endgroup$ – Lorenzo Najt Oct 3 '19 at 13:46
5
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.