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.

Improve this question
$\endgroup$
2
  • $\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$
    – Elle Najt
    Commented Oct 3, 2019 at 13:46
  • 1
    $\begingroup$ You may have more luck here: cstheory.stackexchange.com or here: or.stackexchange.com $\endgroup$
    – Elle Najt
    Commented Oct 3, 2019 at 13:46

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Is the clique problem NP-hard? $\endgroup$
    – dineshdileep
    Commented Oct 3, 2019 at 23:51
  • $\begingroup$ The problem of finding a clique is NP-hard. $\endgroup$
    – LeechLattice
    Commented Oct 4, 2019 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
    Commented Oct 4, 2019 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
    Commented Oct 4, 2019 at 8:05
  • $\begingroup$ The clique problem in $G'$ corresponds to finding a subgraph in $A$ with all edges weighted $1$. $\endgroup$
    – LeechLattice
    Commented Oct 4, 2019 at 8:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .