Problem: given a weighted, connected, undirected graph $$$G$$$, find a spanning tree that minimizes the LCM of its weights.
Is this solvable in polynomial time? Or, can we prove that it's not?
Problem: given a weighted, connected, undirected graph $$$G$$$, find a spanning tree that minimizes the LCM of its weights.
Is this solvable in polynomial time? Or, can we prove that it's not?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
I think it's NP-Hard. From what I've seen here, here you have a graph, each edge has a label, you want to find the minimum spanning tree using the smallest number of labels. I think you can reduce this problem to the one with LCM in the following way: for each distinct label, you consider some distinct very large prime number such that when you take the logarithm of it, all the logs can be approximated to some constant $$$C$$$. In the labeled version, the number of labels that you choose is going to be that constant $$$C \cdot #labels$$$ in the LCM version. Therefore, if you can solve the LCM version, you can also solve the labeled version which is NP-Complete.
If it helps, if the answer is small, you can fix the answer, say it's $$$M$$$, and then check if the graph taken by all the edges that divide $$$M$$$ is connected.
Could you elaborate on what this means? Also, could you explain how to map a given weight $$$w$$$ to a label?
You want to do it the other way, you map labels to weights, because if you were to solve the LCM version polynomially, you could also solve the labelled version polynomially, but that one is proven to be NP-Complete.
When you have a label $$$l_1$$$, you map it to some large prime number, say $$$p_1$$$ that when you compute the log of it, you get something really close to some constant, say $$$\log{p_1} \approx 100$$$. You do this for all labels. When you solve the LCM instance, since all the primes are distinct, the answer is going to be the product of all these primes. When you take the logarithm of that product, you're going to get something very close to $$$100d$$$ where $$$d$$$ is the number of distinct primes that you have in your product. Thus, you take the answer, divide by 100 and round to nearest integer and you get the number of distinct primes, but since for each distinct prime, you have a distinct label in the original problem, $$$d$$$ is going to be the answer also for the label instance, thus you can reduce labelled to LCM, therefore LCM is NP-Hard.
my screen is covered with white now because shsh keeps posting banging blogs
you using light mode or what
shsh orz
Even if said problem is np hard, shsh will probably prove p=np soon...
shsh orz
what are the bounds on the weights? this is rather important i think..... as tinca_matei said, it is definitely np-hard for large weights (even assuming you can multiply in O(1))
also, is there a bound on the answer? otherwise, it can get rather large .....