Is a given graph a k-trail?

From himtp
Revision as of 11:21, 8 December 2015 by Zenklusen (Talk | contribs) (Please add comments here)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

(suggested by András Sebő)

Problem Statement

A k-tree is a tree whose degrees are bounded by k, and a k-trail of a graph is the homomorphic image of a (freely chosen) k-tree onto the vertex set of a graph, where edges are counted with multiplicity.

Question: Can it be decided in polynomial time if a given multigraph is a k-trail (where the multiplicities of the homomorphism must coincide with those of the multigraph)? For fixed k? For k=3?

What is known?

For k=2 the problem is polynomially solvable, since it is equivalent to the existence of an Eulerian trail with possibly a starting point different from the endpoint. Every graph contains a 2-trail, since doubling the edges of an odd join (T-join, where T is the set of odd degree vertices) we get a 2-trail. (If the multiplicities are at most 1 this is NP-hard though. If they are at least one, this is a Chinese postman problem and can be minimized for arbitrary weights.) However, the minimum cardinality 2-trail problem is NP-hard, since it contains the Hamiltonicity of cubic graphs.

Please add comments here

Comment by Rico Zenklusen: Exhibiting a connection to matroids, Mohit Singh and I were able to resolve several open questions asked by András regarding k-trails. In particular, we found an efficient algorithm to check whether a graph is a k-trail. See [1] for more details.