<p>Ok, so as I understand it, you are given as input an undirected graph (representing the "within range" restrictions) with weights on its vertices, and you want to find a non-adjacent pair of vertices that has maximum total weight. I'm going to interpret linear time as being linear in the number of edges in the input graph, not just the number of vertices, because otherwise it doesn't make sense — you need to have enough time to be able to look at the whole input.</p>

<p>Here's an $O(m+n)$ time solution (simplifying an earlier solution I posted here):</p>

<ul>
<li><p>Assume for simplicity that $n$ is a power of two (if not round up).</p></li>
<li><p>Find the median of the vertex weights, the median of the highest $n/2$ vertex weights, the median of the highest $n/4$ vertex weights, etc. These median computations take a total of $O(n)$ time, and once completed they give you the set of $2^i$ largest weights for every choice of an integer $i$ </p></li>
<li><p>For each vertex $v$ with degree $d_v$, let $i_v=\lceil\log_2(d_v+1)\rceil$. Form the pairs $(v,w)$ where $w$ is in the set of $2^{i_v}$ largest vertex weights found during the median calculations.</p></li>
<li><p>From the sets of pairs found in the previous step, remove the pairs that correspond to adjacent pairs of vertices (either by using a hash table of edges for fast adjacency lookup, or by using two passes of bucket sort to make a sorted list of both pairs and input edges).</p></li>
<li><p>The remaining pairs for each vertex $v$ necessarily include the heaviest nonadjacent neighbor of $v$. In particular the heaviest nonadjacent pair in the whole graph is somewhere in this list of pairs. Compute the weight for each pair and choose the max.</p></li>
</ul>

CC BY-SA 3.0
2013-04-24T05:02:30.633Z
2013-04-24T21:44:15.627Z
2013-04-24T21:44:15.627Z
David Eppstein
<p>I have a matrix in the following form:</p>

<pre><code>ID | # Counts for ID | ID's Within Range.
1  | 5               | 1,2,3 
2  | 3               | 1,2
3  | 2               | 1,3
....
</code></pre>

<p>The idea is that I want to find the 2 id's that when you sum the have the highest count. However, you must first exclude the pairs that overlap. For instance, id's 1 and 2 have the highest count but you can't use them since 1 has 2 within range and 2 has 1 within range. Thus from the table above you would use 2,3 as the sum since they don't overlap.</p>

<p>I would like to do this in O(n) or O(nlogn) time and O(n) storage. It's trivial to do if I first make all ID pairs but that gives me O(n^2). I can also do 2 forloops after sorting the list but that would also be at worst O(n^2) although usually much faster... Any help would be greatly appreciated! THanks!</p>

CC BY-SA 3.0
2013-04-23T17:38:41.200Z
Is $n$ the number of IDs or the number of overlaps?  If it's the number of IDs, you can't even read the entire input in $O(n)$ time.
Jeffε
CC BY-SA 3.0
2013-04-23T18:14:56.367Z
If there are n rows, why would it not take O(n) to read it? Each row is read at some constant. Thus it takes c per row, cn total -> O(n). You can assume the matrix is already constructed and you don't need to figure out the overlaps. You can just read them in.
user1357015
CC BY-SA 3.0
2013-04-24T03:33:27.600Z
it's not even about word RAM, the problem is how long is the list of IDs within range for each ID. The time to read the input is the total length of all these lists.
Sasho Nikolov
CC BY-SA 3.0
2013-04-24T15:19:33.327Z
Specifically: As you've described the problem, each of the $n$ IDs could overlap $n-1$ other IDs.  So you **cannot** read each row in constant time.
Jeffε
<ds.algorithms><time-complexity><sorting>
Finding max of two elements in linear time with restriction
user1357015
# Finding max of two elements in linear time with restriction

(Asked by: username_0 on 2013-04-23)

I have a matrix in the following form:
ID | # Counts for ID | ID's Within Range.
1  | 5               | 1,2,3 
2  | 3               | 1,2
3  | 2               | 1,3
....

The idea is that I want to find the 2 id's that when you sum the have the highest count. However, you must first exclude the pairs that overlap. For instance, id's 1 and 2 have the highest count but you can't use them since 1 has 2 within range and 2 has 1 within range. Thus from the table above you would use 2,3 as the sum since they don't overlap.
I would like to do this in O(n) or O(nlogn) time and O(n) storage. It's trivial to do if I first make all ID pairs but that gives me O(n^2). I can also do 2 forloops after sorting the list but that would also be at worst O(n^2) although usually much faster... Any help would be greatly appreciated! THanks!

**Tags:** ds.algorithms, time-complexity, sorting
> **Comments:**
> **username_1**: Is $n$ the number of IDs or the number of overlaps?  If it's the number of IDs, you can't even read the entire input in $O(n)$ time.  
> **username_0**: If there are n rows, why would it not take O(n) to read it? Each row is read at some constant. Thus it takes c per row, cn total -> O(n). You can assume the matrix is already constructed and you don't need to figure out the overlaps. You can just read them in.  
> **username_2**: it's not even about word RAM, the problem is how long is the list of IDs within range for each ID. The time to read the input is the total length of all these lists.  
> **username_1**: Specifically: As you've described the problem, each of the $n$ IDs could overlap $n-1$ other IDs.  So you **cannot** read each row in constant time.  

---

## 1 answers

### Answer by username_3 on 2013-04-24. Score: 11 | Accepted answer

Ok, so as I understand it, you are given as input an undirected graph (representing the "within range" restrictions) with weights on its vertices, and you want to find a non-adjacent pair of vertices that has maximum total weight. I'm going to interpret linear time as being linear in the number of edges in the input graph, not just the number of vertices, because otherwise it doesn't make sense — you need to have enough time to be able to look at the whole input.

Here's an $O(m+n)$ time solution (simplifying an earlier solution I posted here):

* Assume for simplicity that $n$ is a power of two (if not round up).
* Find the median of the vertex weights, the median of the highest $n/2$ vertex weights, the median of the highest $n/4$ vertex weights, etc. These median computations take a total of $O(n)$ time, and once completed they give you the set of $2^i$ largest weights for every choice of an integer $i$
* For each vertex $v$ with degree $d\_v$, let $i\_v=\lceil\log\_2(d\_v+1)\rceil$. Form the pairs $(v,w)$ where $w$ is in the set of $2^{i\_v}$ largest vertex weights found during the median calculations.
* From the sets of pairs found in the previous step, remove the pairs that correspond to adjacent pairs of vertices (either by using a hash table of edges for fast adjacency lookup, or by using two passes of bucket sort to make a sorted list of both pairs and input edges).
* The remaining pairs for each vertex $v$ necessarily include the heaviest nonadjacent neighbor of $v$. In particular the heaviest nonadjacent pair in the whole graph is somewhere in this list of pairs. Compute the weight for each pair and choose the max.


---

