search

math1um / objects-invariants-properties

Objects, Invariants and Properties for Graph Theory (GT) automated conjecturing: in particular with the Sage program CONJECTURING: http://nvcleemp.github.io/conjecturing/
GNU General Public License v3.0
15 stars 6 forks source link

Add invariant: path_covering_number #533

Open math1um opened 6 years ago

math1um commented 6 years ago

This is the minimum number of disjoint (not necessarily induced) paths that contain (cover) all of the vertices of the graph.

path_covering_number = 1, for any path path_covering_number = 1, for any hamiltonian graph path_covering_number = n-2, for any non-degenerate star (n>2, in this case n-3 of the paths will be single vertices), where n is the order.

This will be hard to compute. Its not even clear what an algorithm might look like. An obvious upper bound is n (take n 1-vertex paths).

It was first defined in:

Ore, Oystein. "Arc coverings of graphs." Annali di Matematica Pura ed Applicata 55.1 (1961): 315-321. (attached)

ore-arc-coverings-1961.pdf

yirkajk commented 6 years ago

The ideal would be if we can prove a greedy algorithm works. Basically, can we just find the longest path in the graph, then the longest path in the remaining graph, then the next, and so on?

nvcleemp commented 6 years ago

A bound that might be useful (or not) is the following. Define the minimum leaf number of G as the least number of leaves in a spanning tree of G. We then have:

path_covering_number(G) + 1 <= minimum_leaf_number(G) <= 2 path_covering_number(G)

math1um commented 6 years ago

Greedy will give you a bound. It will fail in general: path_covering_number = 1 iff the graph has a hamiltonian path. If it worked, greedy would give a fast algorithm for traceability!

nvcleemp commented 6 years ago

Yes, but Justin's proposal is not to find the path greedily, but to first find a longest path, and then again a longest path in the remaining graph. This still is NP.

However I doubt this approach will work.

math1um commented 6 years ago

Yep, take a milkbone graph (2 p3s with the middle vertices joined by an edge). the path covering number = 2, but this algorithm will give 3.

yirkajk commented 6 years ago

Okay, so greedy based on path length doesn't work. Maybe max path length over minimize disconnected components. So never disconnect the graph earlier than necessary, but within that restriction, we maximize the path length. This would work on the milk bone.

I'm just throwing out ideas as they pop up.