Ask Your Question
1

Number of disjoint hamiltonian cycles in a graph

asked 2022-12-02 16:26:06 +0100

vidyarthi gravatar image

updated 2022-12-04 12:22:24 +0100

I wish to obtain the maximum number of mutually disjoint hamiltonian cycles in a given graph. Is there any command in SageMath to do it. I think of iterating over getting the hamiltonian cycle of the graph using G.hamiltonian_cycle() function, by deleting the edges of the cycles obtained at each successive iteration from the graph. However, is there a built-in function in SageMath for this? Thanks beforehand.

edit retag flag offensive close merge delete

Comments

2

We don't have such method in Sagemath. This is a hard optimisation problem. You can use integer linear programming to model and solve it.

David Coudert gravatar imageDavid Coudert ( 2022-12-02 18:16:15 +0100 )edit
1

Also, your question is not entirely clear. You want the maximal number of pairwise disjoint hamiltonian cycles? I doubt that starting with a random hamiltonian cycle (such as given by G.hamiltonian_cycle()), deleting it and repeating the procedure would give this maximum. If you want a maximal collection of pairwise disjoint hamiltonian cycles (ie such that what remains is not hamiltonian) your suggestion would certainly works.

vdelecroix gravatar imagevdelecroix ( 2022-12-02 21:18:13 +0100 )edit

@vdelecroix yes, I want the maximum number of disjoint hamiltonian cycles in a graph. Yes, my method would work for maximal, but I actually wanted maximum of such cycles. edited the question

vidyarthi gravatar imagevidyarthi ( 2022-12-03 16:28:10 +0100 )edit

@David Coudert thanks, but could you just slightly elaborate?

vidyarthi gravatar imagevidyarthi ( 2022-12-03 16:28:51 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
4

answered 2022-12-04 12:40:53 +0100

This method will return the maximum number of edge disjoint Hamiltonian cycles. This is certainly not the best possible formulation.

def disjoint_hamiltonian_cycles(g, solver=None, verbose=0,
                                *, integrality_tolerance=1e-3):
    """
    """
    from sage.numerical.mip import MixedIntegerLinearProgram
    from sage.numerical.mip import MIPSolverException
    from sage.graphs.graph import Graph

    UB = min(g.degree()) // 2
    if not UB:
        raise EmptySetError("the given graph is not Hamiltonian")

    eps = 1 / (2*Integer(g.order()))
    x = next(g.vertex_iterator())

    while True:
        # Search for UB edge disjoint Hamiltonian cycles
        p = MixedIntegerLinearProgram(solver=solver)

        f = p.new_variable(binary=True)
        r = p.new_variable(nonnegative=True)

        # An edge belongs to a unique cycle
        for e in g.edge_iterator(labels=False):
            p.add_constraint(p.sum(f[frozenset(e), i] for i in range(UB)) <= 1)

        # All the vertices of cycle i have degree 2
        for i in range(UB):
            for v in g:
                p.add_constraint(p.sum(f[frozenset((u, v)), i] for u in g.neighbor_iterator(v)), min=2, max=2)

        # Connectivity constraints based on the maximum average degree
        for i in range(UB):
            # r is greater than f
            for u, v in g.edge_iterator(labels=None):
                p.add_constraint(r[u, v, i] + r[v, u, i] - f[frozenset((u, v)), i], min=0)

            # no cycle which does not contain x
            for v in g:
                if v != x:
                    p.add_constraint(p.sum(r[u, v, i] for u in g.neighbor_iterator(v)), max=1 - eps)

        try:
            p.solve(log=verbose)
            f_val = p.get_values(f, convert=bool, tolerance=integrality_tolerance)
            tsp = [Graph() for i in range(UB)]
            for i in range(UB):
                tsp[i].add_vertices(g.vertex_iterator())
                tsp[i].set_pos(g.get_pos())
            for (e, i), b in f_val.items():
                if b:
                    tsp[i].add_edge(e)
            return tsp

        except MIPSolverException:
            UB -= 1
            if not UB:
                raise EmptySetError("the given graph is not Hamiltonian")

You get:

sage: G = graphs.CompleteGraph(5)
sage: T = disjoint_hamiltonian_cycles(G)
sage: T
[Graph on 5 vertices, Graph on 5 vertices]
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 3), (1, 4), (2, 3), (2, 4)],
 [(0, 2), (0, 4), (1, 2), (1, 3), (3, 4)]]
sage: G = graphs.CompleteGraph(7)
sage: T = disjoint_hamiltonian_cycles(G)
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 4), (1, 6), (2, 3), (2, 5), (3, 6), (4, 5)],
 [(0, 2), (0, 5), (1, 3), (1, 4), (2, 6), (3, 5), (4, 6)],
 [(0, 3), (0, 6), (1, 2), (1, 5), (2, 4), (3, 4), (5, 6)]]
edit flag offensive delete link more

Comments

Thanks! that is so kind of you! Actually, I wanted just the maximum number of disjoint hamiltonian cycles, but you gave the full construction. Anyways, the len() would suffice for my needs

vidyarthi gravatar imagevidyarthi ( 2022-12-04 20:01:25 +0100 )edit

Note that the number of edge disjoint Hamiltonian cycles is upper bounded by half the minimum degree of the graph

sage: G = graphs.CompleteGraph(5)
sage: min(G.degree()) // 2
2
sage: G = graphs.CompleteGraph(7)
sage: min(G.degree()) // 2
3
David Coudert gravatar imageDavid Coudert ( 2023-02-18 09:33:44 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

2 followers

Stats

Asked: 2022-12-02 16:26:06 +0100

Seen: 251 times

Last updated: Dec 04 '22

Related questions