[Edit 01/02/2021] : Now the problem has been identified, as a relaxation of "minimal spanning tree" (it is more a minimal spanning sub-graph). Are they some references I could use on this problem ?
Let consider a graph made of $N$ nodes, numeroted from $B_1$ to $B_N$.
Each nodes can or cannot be connected to the other nodes, but overall we consider a family of weighed edges : $(\nu_{ij})_{1 \leq i < j \leq N} \in \mathbb{R}^{\frac{N(N-1)}{2}}$.
The edges must be understood as followed :
$\nu_{ij}=0$ if $B_i$ and $B_j$ are not linked by an edge.
there is no edge connecting one node to himself.
I want to operate with a specific way on this graph (I want to select some specific edges), and I believe I am looking for a family of numbers $(x_{ij})_{1 \leq i < j \leq N}$ with $x_{ij}=0$ or $1$ that verifies the following discrete optimization problem :
$$\underset{(x_{ij})_{1 \leq i < j \leq N} \in (0,1)^{\frac{N(N-1)}{2}}}{\min} \sum_{i<j}\ \nu_{ij} \ x_{ij}$$ with the following constraints on the $(x_{ij})$:
- $\sum_{i<j} x_{ij} = N-1$ (i.e we are only gonna keep $N-1$ edges in the graph)
- $\forall i \in \{1,\dots,N\}$, we have $$\sum_{j=i+1}^N x_{ij} + \sum_{j=1}^{i-1} x_{ji} \geq 1$$ (i.e every nodes have at least one "non-zero" edge)
My questions
Is this problem known in operation research or discrete optimization or is it closed to a known problema with a theoritical analysis ? I don't know a lot of them, except for the traveling salesman problem or the cover set problem but I am quite unfamiliar with them.
Separately from this first question, I believe (heuristically, at least) that any family $(x_{ij})_{1 \leq i < j \leq N}$ admissible for this problem verifies the following property :
the final graph with value $(x_{ij} \nu_{ij})$ on the edge is made of cycles and of only one path
But i am not sure how to prove it. I'have been looking for counter-examples using $4/5$ nodes and cycle but couldn't find any... Any help, references or remarks are welcomed on the problem :).
(I assume here that your edges' costs are in $\mathbb R_+^* \cup \{+\infty\}$)
First, you can remove the $\Sigma x_{ij} = N+1$ constraint. If you have a minimum-cost solution, it will be a forest covering all the nodes (since if there was a cycle, you could remove its biggest edge, and the "non-zero degree" constraint will still be preserved at a better cost). Given this minimum-cost solution, if you want to add edges to add up to $N+1$ edges, you can use the smallest edges that aren't used yet.
So now you just need a minimum-size edge cover of the vertices, and this has a polynomial solution (see https://en.wikipedia.org/wiki/Edge_cover) EDIT : The Wikipedia page only cites the problem with constant-valued edges. A polynomial solution also exists for the real-valued one : see [Plesník, Ján, Equivalence between the minimum covering problem and the maximum matching problem, Discrete Math. 49, 315-317 (1984). ZBL0581.05045.]
Concerning the shape of the solution, it turns out that, in this minimum-cost forest, you won't have a 3-length path. If you have a chain $u - v - w - x$ then the same forest without the $(u,v)$ edge still works for the constraints and has a lower cost. So the solution is a collection of trees whose diameter is 1 or 2 : those are stars (https://en.wikipedia.org/wiki/Star_(graph_theory)). But then, you just fill it with the smallest edges you get, so you could have any graph shape.