Opened 6 years ago

Closed 6 years ago

# path_decomposition just returns vertex_separation output, it should derive the path decomposition instead

Reported by: Owned by: Rolf Morel minor sage-7.5 graph theory vertexseparation, vertex_separation, pathdecomposition, path_decomposition, pathwidth David Coudert Rolf Morel N/A 39822e8 39822e8772127bdd0b939d0bc5a01332977ae7f6

### Description

Hi,

I am new to contributing to sage, so please bear with me.

Currently path_decomposition for graphs (in sage/graphs/graph_decompositions/vertex_separation) is implemented as no more than a wrapper round the vertex_separation function. While there exists a close relation between path decompositions and vertex separation it would be more natural to have path_decomposition return the pathwidth and an actual path decomposition, versus the current behaviour of returning the vertex separation number and a linear ordering that achieves this vertex separation number.

Due to Kinnersley [1], we know the vertex separation number is equal to the pathwidth and that there exists a simple mapping between a linear ordering for the vertex separation (number) of a graph and a path decomposition for the same graph. I already have an algorithm implementing this mapping on top of sage, but I would like to see that the path_decomposition function in sage actually returns a path decomposition, along side the pathwidth. Also, the current behaviour does not have much added value, if you wanted the pathwidth you could have just used the vertex_separation function.

Finally as the algorithms to compute the vertex separation (number) and pathwidth run in exponential time the cost of doing the mapping (in O(|V|2|E|) time) is minor, and anybody wanting to forgo the cost of the mapping (because they are only interested in the pathwidth) could just call vertex_separation directly.

I am currently compiling sage in the hope of creating a patch. Please let me know if the ability to compute path decompositions would be considered a useful addition to sage.

A question regarding stability in sage: would it be considered better to modify the current path_decomposition function so as to return the pathwidth and a path decomposition, or would the current behaviour be considered stable and hence there would need to be some separate function to derive the path decomposition?

[1] The vertex separation number of a graph equals its path-width, Nancy G. Kinnersley, Information Processing Letters 42(6):345-350, 1992.

### comment:1 Changed 6 years ago by Rolf Morel

Keywords: "vertex separation" "path decomposition" added; vertex separation path decomposition removed

### comment:2 Changed 6 years ago by Rolf Morel

Keywords: vertexseparation vertex_separation pathdecomposition path_decomposition added; "vertex separation" "path decomposition" removed

### comment:4 Changed 6 years ago by David Coudert

Welcome. I can certainly help here.

We could add a method `pathwidth` with similar behavior than `treewidth`. Then we can change the behavior of `path_decomposition` but we must add an appropriate warning message (decprecation?).

What's your algorithm? the announced complexity seems excessive. I believe it can be done in `O(|V|*|E|)` or even `O(|E|)`.

### comment:5 Changed 6 years ago by Rolf Morel

Yes, bringing `pathwidth` in line with the current `treewidth` API seems like an appropriate change as well.

The initial algorithm that I put together for decompositions is just a straightforward translation of the constructive proof for Theorem 3.1 in The vertex separation number of a graph equals its path-width by Kinnersley. Here is the function:

```def decomposition1(g):
pw, l_ord = vertex_separation(g)
decomp = []
def l_cut(i):
for j in range(i + 1):
if any(n in l_ord[i+1:] for n in g.neighbors(l_ord[j])):
yield l_ord[j]
for i, i_node in enumerate(l_ord):
decomp.append([i_node] + list(l_cut(i-1)))
return pw, decomp
```

I had not considered efficiency much (yet) for the above algorithm, but due to your comment I came up with a `O(pw(G)*|V| + |E|)` algorithm. It builds on the previous algorithm. The first idea is to keep track of the maximum linear ordering index of a connected node per vertex, which makes it an amortized `O(1)` lookup whether a vertex at index `j` connects to another vertex at some index `m` of the ordering with `m > i` for any position `i` within the ordering (which is essentially the check in `l_cut`).

For constructing a `bag_i` for a vertex at index `i` in the ordering we again consider all nodes before `i` in the ordering but now we exploit the property of path decompositions that if a bag shares vertices with a previous bag, then all intermediate bags must also contain those vertices. So in particular the previous bag must contain all nodes that are in `bag_i` (except for the node at `i`) and before `i` in the ordering. So it suffices to check if the vertices of the previous bag are (still) connected to vertices beyond `i` in the ordering.

(Note that the current psuedo code assumes undirected edges.)

```def decomposition2(g):
pw, l_ord = vertex_separation(g)

decomp = []
l_ord_inv = {v : i for i, v in enumerate(l_ord)}
max_l_ord_idx_of_neighs = {}
for u, v, label in g.edges():
old_max_u = max_l_ord_idx_of_neighs.get(u, l_ord_inv[u])
max_u = max(l_ord_inv[v], old_max_u)
max_l_ord_idx_of_neighs[u] = max_u
old_max_v = max_l_ord_idx_of_neighs.get(v, l_ord_inv[v])
max_v = max(l_ord_inv[u], old_max_v)
max_l_ord_idx_of_neighs[v] = max_v

for i in range(len(l_ord)):
bag_i = [l_ord[i]]
prev_bag = decomp[i-1] if i >= 1 else []
for vert_prev_bag in prev_bag:
if max_l_ord_idx_of_neighs[vert_prev_bag] >= i:
bag_i.append(vert_prev_bag)
decomp.append(bag_i)
return pw, decomp
```

There might still be some clever tricks to get the runtime further down, but versus the runtime of `vertrex_separation` it does not seem worth the effort.

Note that while these functions give correct path decompositions they produce `|V|` bags, while sometimes it is possible to do with less. A simple algorithm to produce less bags is to check for each bag (consecutively) if it is a proper subset of the next bag. Would this be a worthwhile addition?

And finally, any pointers for contributing the code to `sage`?

### comment:6 Changed 6 years ago by David Coudert

There is something wrong with both methods, although the principle is good.

```sage: G = graphs.PathGraph(5)
sage: decomposition1(G)
(1, [[0], [1, 0], [2, 1], [4, 2], [3, 2, 4]])
sage: decomposition2(G)
(1, [[0], [1, 0], [2, 1], [4, 2], [3, 4, 2]])
```

I prefer the following method.

```def linear_ordering_to_path_decomposition(G, L):
"""
"""
from sage.graphs.graph_decompositions.vertex_separation import is_valid_ordering
if not is_valid_ordering(G, L):
raise ValueError("The input linear vertex ordering L is not valid for G.")

seen    = set()  # already treated vertices
covered = set()  # vertices in the neighborhood of seen but not in seen
bags    = list() # The bags of the path decomposition

# We build the bags of the path-decomposition, and avoid adding useless bags
for u in L:
covered.update(G.neighbors(u))
covered.difference_update(seen)
new_bag = covered.union([u])
if bags:
if new_bag.issubset(bags[-1]):
continue
if new_bag.issuperset(bags[-1]):
bags.pop()

bags.append(new_bag)

# We now build a graph whose vertices are bags
H = Graph()
print bags

return H
```

To start contributing, you can check http://doc.sagemath.org/html/en/developer/index.html and http://doc.sagemath.org/html/en/developer/manual_git.html

So you create a new git branch on your local sage installation. You do your changes (preferably with clear commits) and when you are ready, you push your changes to the trac server.

If you prefer, you can start as a reviewer: I do the changes and I soon as it's on the server, you can review it. You then have to check the code, try to install/compile on your system, play with it, check if it gives good answer, etc.

Let me know.

### comment:7 Changed 6 years ago by David Coudert

Authors: → David Coudert → u/dcoudert/pathwidth → 39822e8772127bdd0b939d0bc5a01332977ae7f6 new → needs_review

I have pushed a proposal for discussed issues: expose method pathwidth with similar behavior than treewidth. Let me know if something is missing.

New commits:

 ​65cadd2 `trac #22045: add method to compute a path decomposition from an ordering` ​a64a67c `trac #22045: add method to compute pathwidth` ​44cbb14 `trac #22045: expose method pathwidth for graphs` ​39822e8 `trac #22045: fix doc and examples`

### comment:8 Changed 6 years ago by Rolf Morel

The problem that you identified with the functions seems to originate from the `vertex_separation` function. While the vertex separation number is correct (for the path graphs) the linear ordering that is returned does not seems like a proper witness/certificate to this vertex separation number.

```sage: G = graphs.PathGraph(3)
sage: G.edges()
[(0, 1, None), (1, 2, None)]
sage: vertex_separation_BAB(G)  # correct vertex separation number, incorrect ordering
(1, [0, 2, 1])
sage: vertex_separation_MILP(G) # correct vertex separation number, incorrect ordering
(1, [0, 2, 1])
sage: vertex_separation_exp(G)  # correct vertex separation number, and correct ordering
(1, [0, 1, 2])
```

Note that for the Branch and Bound and MILP algorithms the ordering has node 2 in the middle, which means that both it and node 0 to the left of it have a neighbor to the right of node 2, namely node 1 (third in the ordering). So by the definition of vertex separation (of an ordering) the vertex separation for this ordering is 2. While the exponential algorithm gives the correct witness to the vertex separation number being equal to 1.

Unless there is some kind of misunderstanding, it seems like the `vertex_separation_BAB` and `vertex_separation_MILP` do not give correct output. In particular sometimes they do not give back the linear ordering that acts as a witness to the vertex separation number that was found.

It seems prudent to me to first clear this up before looking into incorporating new code for path decompositions.

Would very much like to know what is going on here.

### comment:9 Changed 6 years ago by David Coudert

The way to measure the width of an ordering used in this module is clearly presented at the beginning of the module's documentation. It is equivalent to [1], up to reversing the ordering. I have to say that it is more intuitive for me to count the number of neighbors on the right of the nodes on the left, than the number of nodes of the left that have a neighbor on the right. The simple method I wrote to go from an ordering to a decomposition is based on this.

If you want your methods to return correct results, just add `l_ord.reverse()` inside.

[1] Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos: A Note on Exact Algorithms for Vertex Ordering Problems on Graphs. Theory Comput. Syst. 50(3): 420-432 (2012) http://dx.doi.org/10.1007/s00224-011-9312-0

### comment:10 Changed 6 years ago by David Coudert

Any help reviewing this patch is more than welcome.

### comment:11 Changed 6 years ago by Rolf Morel

Apologies for taking so long to get back to this. I looked at it some time ago and didn't understand your algorithm (with the notion of the ordering reversed). Decided to get back to it later and that got postponed.

Thank you for clearing up the matter of the orderings. The vertex separations I tried on a my limited number of test graphs happened to be okay even if they were reversed and with only knowledge of the other definition I didn't look in detail at the definition given at the top of the file.

I verified the properties of a path decomposition with pathwidth equal to the vertex separation for your algorithm and they are indeed fine. I ran the `pathwidth` method on a couple of graphs and this seems to work fine as well.

So, looks good to me.

### comment:12 Changed 6 years ago by David Coudert

Have you tried to run the doc tests using a command like `sage -btp src/sage/graphs/graph_decompositions/vertex_separation.pyx` ? same with `graph.py` since this patch exposes the method for `Graph`. You can also try to build the doc using e.g. `sage -docbuild reference/graphs html` and check if it looks good. If everything is ok, then you can set the patch to positive review, or let me know if I should improve something.

It will now be easier to verify if a graph is asteroidal triple free graphs then we have treewidth = pathwidth ;)

By the way, I could change ref CMN14 with the journal version, but it's not so important.

### comment:13 Changed 6 years ago by Rolf Morel

Status: needs_review → positive_review

Ran the tests you suggested and checked the documentation. All the tests passed and the docs look fine. Everything seems okay from here.

### comment:14 Changed 6 years ago by Travis Scrimshaw

You will need to put your real name as the reviewer.

### comment:15 Changed 6 years ago by Rolf Morel

Reviewers: → Rolf Morel

I put my real name in the 'Reviewers' field.

### comment:16 Changed 6 years ago by David Coudert

Thanks for the review.

### comment:17 Changed 6 years ago by Volker Braun

Branch: u/dcoudert/pathwidth → 39822e8772127bdd0b939d0bc5a01332977ae7f6 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.