I have a partiuclar kind of graph problem and (not having a background in graph algorithms) I would like to know how this kind of problem is called in the literature and what algorithms exist for solving it.

I have an undirected graph consisting of vertices $V$ and edges $E$. Each edge has a potential $p_e \in [0..1]$

Independently of the edge potentials there is also edge weights $w_e \in \{0,1\}$ that turn on/off an edge and connect or disconnect two vertices. The number of 1-weight-edges of a vertex let's call $n$, which is the "connectedness" (or "subgraph-degree") of a vertex.

In our problem edge potentials are given and edge weights are what we look for.

Let's then call $s_e=p_e*w_e$ the "strength" of an edge. Also, for any two vertices, if there's an indirect connection the strength of the indirect connection is the product of all strengths $s_e$ along the path. The strength of the shortest connection between two vertices let's call $t_e$.

So, the problem is: for a given global $n$ (same for all vertices) how can I find weights $w_e$ for each edge resulting in the "best" interconnectivity for the graph, the one that maximizes the sum of $t_e$?

In other words: Having a given (usually small) $n$, I would like to choose $n$ out of many existing edges for each vertex such that the resulting graph is "nicely" connected. That means that the algorithm would favor connecting two vertices with a somewhat lower $p_e$ over connecting vertices with a higher $p_e$ but who already have a pretty good indirect connection.

Update: According to the comment below I am looking for the $n$-regular edge-induced subgraph that maximizes the sum of all $t_e$.

I have a hunch that this might be NP hard but any approximate solutions would be appreciated too.

  • $\begingroup$ the jargon is like finding the "n-regular" "edge-induced subgraph", for a given graph and a given n, that maximizes whatever connectivity objective $\endgroup$ – k20 Jul 11 '14 at 18:24
  • $\begingroup$ FWIW, can you reduce HAMPATH to it? Given unweighted undirected graph G=(V,E), assign potential 1 to each edge, add all missing edge and given them potential 0. Then consider it as an instance of your problem with n=2. If there is a Hamiltonian path, then the answer is (|V| choose 2), otherwise it is less. $\endgroup$ – Neal Young Jul 13 '14 at 16:31

Your Answer

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

Browse other questions tagged or ask your own question.