Timeline for What does the basis of the null space of the constraint matrix of a flow problem look like?
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 17, 2019 at 9:59 | vote | accept | Ricardo | ||
| Feb 27, 2018 at 17:12 | answer | added | Peter Heinig | timeline score: 4 | |
| Aug 23, 2017 at 22:50 | comment | added | Aaron Dall | If you want a basis encoded by graph data, try searching for "cycle space basis" and/or "fundamental cycles". The null space of the constraint matrix is called the cycle space of the graph because it is spanned by the (signed) incidence vectors of the cycles. Although the cycles span the space, there are typically more than rank many of them. One way to choose a basis from among the cycles is to fix a spanning forest $F$ of $G$ and take, for each edge $e \in G \setminus F$, the unique cycle in $F \cup \{e\}$. These are the fundamental cycles of $G$ with respect to $F$ and they form a basis. | |
| Aug 19, 2017 at 10:26 | comment | added | Ricardo | See: pdfs.semanticscholar.org/396b/… Thm 30, p. 19 | |
| Aug 19, 2017 at 10:26 | comment | added | Ricardo | The background: There is a result by Bienstock&Zuckerberg for the precedence constraints of the max closure problem. The null space of this constraint matrix has a basis composed of connected components in some graph derieved from the original graph. This is then used to bound the number of connected components and thus the size of the basis. They then prove that LP solution values inside a connected component have always the same fractional value, thus they obtain a bound on the number of different fractional values in their LP solutions. | |
| Aug 19, 2017 at 10:22 | comment | added | Ricardo | I don't need the answer to that question urgently. I'll try to specify my question and to provide some additional context. I know so far: A basis can be obtained from the generating set of all simple cycles(ignoring orientation). My questions are: Is there a "canonical" basis that is well-known? Are there specific properties for cycles that are in a basis? Can we tell something about how much these cycles "overlap"(share edges)? Is there a basis with a different combinatorial meaning?.... | |
| Aug 18, 2017 at 12:58 | comment | added | Peter Heinig | Dear @Ricardo: I am asking since I think you asked a very broad question, which nevertheless in its substance is legitimate (there are related, rather natural open questions even). Yet I will not, as a matter of principle, post a half-baked, uncompressed, unsatisfactory answer. I will be writing you a summarizing, compressed answer, yet this will take some time. Very briefly, I think the essence is not how these bases do look like, but rather what they can look like. I think it is making better use of the MO medium to ask whether you need to urgently know something specific. | |
| Aug 18, 2017 at 9:04 | comment | added | Peter Heinig | Dear @Ricardo: I think I know much about what you seem to be asking for, and, having studied this as a graduate student, I think I even have what is often called a 'big picture' of this topic (as opposed to many relevant yet undigested references), yet writing a compressed/informative answer takes more time than I currently have. So, to take the remit of this site really seriously, I feel obliged to ask: do you urgently need to know someting specific? If so, please ask the specific question. | |
| Aug 16, 2017 at 11:37 | comment | added | Ricardo | @JohnGunnarCarlsson All incidence vectors of cycles are in the kernel. Also all incidence vectors of cycles that "disregard orientation" are in the kernel if we swap some one entries for -1, to obtain a cycle with correct orientation. I assume they span the whole kernel. There are cases however when we can construct simple cycles from other simple cycles. So we wouldn't get a basis but just a generating set. | |
| Aug 16, 2017 at 11:34 | comment | added | Ricardo | You're right, I've fixed it. Look = I want to be able to describe a basis in combinatorial terms or give a closed representation. | |
| Aug 16, 2017 at 11:13 | history | edited | Ricardo | CC BY-SA 3.0 | added 62 characters in body |
| Aug 16, 2017 at 5:50 | comment | added | Peter Heinig | Dear @Ricardo, I think $A\in\mathbb{N}^{\lvert V\rvert\times\lvert\mathbb{R}\rvert}$ is meaningless, though it does 'parse' (as they say): if one takes this seriously, then $\lvert\mathbb{R}\rvert$ is the cardinality $\mathfrak{c}$ of the continuum, and the expression you gave is the set of all functions $\lvert V\rvert\times\mathfrak{c}\rightarrow \mathbb{N}$, where $\lvert V\rvert$ is the cardinality of $V$. I think what you mean is $A\in \mathbb{N}^{V\times\mathbb{A}}$, obviously. Would you please clarify whether you agree with this, and, more importantly, what do you mean by 'look'? | |
| Aug 16, 2017 at 4:58 | comment | added | John Gunnar Carlsson | Isn't it just cycles in $G$? (Unless I have misunderstood something) | |
| S Aug 15, 2017 at 22:41 | history | suggested | Rodrigo de Azevedo | Added tags | |
| Aug 15, 2017 at 21:44 | review | Suggested edits | |||
| S Aug 15, 2017 at 22:41 | |||||
| Aug 15, 2017 at 13:56 | review | First posts | |||
| Aug 15, 2017 at 13:58 | |||||
| Aug 15, 2017 at 13:53 | history | asked | Ricardo | CC BY-SA 3.0 |