Revision history [back]

This is a typical universal cover problem which can be solved using Knuth dancing links' algorithm:

def has_claw_decomposition(G, certificate=False):
    import itertools
    from sage.combinat.matrices.dancing_links import dlx_solver

    rows = []

    id_to_edge = [frozenset(edge) for edge in G.edges(labels=False)]
    edge_to_id = {edge:i for (i,edge) in enumerate(id_to_edge)}

    for u in G:
        u_neighbors = G.neighbors(u)

        for three_neighbors in itertools.combinations(u_neighbors, 3):
            L = [edge_to_id[frozenset((u,v))] for v in three_neighbors]
            L.sort()
            rows.append(L)

    d = dlx_solver(rows)

    solution = d.one_solution()
    has_solution = not solution is None

    if not certificate:
        return has_solution
    else:
        if has_solution:
            solution_vertices = [[tuple(id_to_edge[id]) for id in rows[row_number]]
                                 for row_number in solution]
            return (has_solution, solution_vertices)
        else:
            return (has_solution, solution)

The first graph:

sage: from slabbe.graph import has_claw_decomposition
sage: G1 = Graph( [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3),
....: (1, 5), (2, 3), (2, 4), (3, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 8),
....: (6, 10), (7, 9), (7, 11), (8, 9), (8, 10), (9, 11), (10, 11)])
sage: has_claw_decomposition(G1)
False
sage: has_claw_decomposition(G1, certificate=True)
(False, None)

The second graph:

sage: G2 = Graph([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4),
....:    (1, 5), (2, 4), (2, 5), (3, 5), (4, 5)])
sage: has_claw_decomposition(G2)
True
sage: has_claw_decomposition(G2, certificate=True)     # random
(True,
 [[(0, 1), (1, 2), (1, 5)],
  [(0, 3), (1, 3), (3, 5)],
  [(0, 2), (2, 4), (2, 5)],
  [(0, 4), (1, 4), (4, 5)]])

Actually, I wrote the code as a new function inside the graph module of my package. It could move up to sage if it is desirable, perhaps once it is generalized to any subgraph, for instance using the graph method subgraph_search_iterator().

Note that dancing links allows to enumerate all solutions. Also, there is a method to solve the dlx using sat solvers or milp solvers. See the documentation of dlx solver in sagemath here for more information.

This is a typical universal cover problem which can be solved using Knuth dancing links' algorithm:

def has_claw_decomposition(G, certificate=False):
    import itertools
    from sage.combinat.matrices.dancing_links import dlx_solver

    rows = []

    id_to_edge = [frozenset(edge) for edge in G.edges(labels=False)]
    edge_to_id = {edge:i for (i,edge) in enumerate(id_to_edge)}

    for u in G:
        u_neighbors = G.neighbors(u)

        for three_neighbors in itertools.combinations(u_neighbors, 3):
            L = [edge_to_id[frozenset((u,v))] for v in three_neighbors]
            L.sort()
            rows.append(L)

    d = dlx_solver(rows)

    solution = d.one_solution()
    has_solution = not solution is None

    if not certificate:
        return has_solution
    else:
        if has_solution:
            solution_vertices = [[tuple(id_to_edge[id]) for id in rows[row_number]]
                                 for row_number in solution]
            return (has_solution, solution_vertices)
        else:
            return (has_solution, solution)

The first graph:

sage: from slabbe.graph import has_claw_decomposition
sage: G1 = Graph( [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3),
....: (1, 5), (2, 3), (2, 4), (3, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 8),
....: (6, 10), (7, 9), (7, 11), (8, 9), (8, 10), (9, 11), (10, 11)])
sage: has_claw_decomposition(G1)
False
sage: has_claw_decomposition(G1, certificate=True)
(False, None)

The second graph:

sage: G2 = Graph([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4),
....:    (1, 5), (2, 4), (2, 5), (3, 5), (4, 5)])
sage: has_claw_decomposition(G2)
True
sage: has_claw_decomposition(G2, certificate=True)     # random
(True,
 [[(0, 1), (1, 2), (1, 5)],
  [(0, 3), (1, 3), (3, 5)],
  [(0, 2), (2, 4), (2, 5)],
  [(0, 4), (1, 4), (4, 5)]])

Actually, I wrote the code as a new function inside the graph module of my package. It could move up to sage if it is desirable, perhaps once it is generalized to any subgraph, for instance using the graph method subgraph_search_iterator().

Note that dancing links allows to enumerate enumerate/count all solutions. Also, there is a method to solve the dlx using sat solvers or milp solvers. See the documentation of dlx solver in sagemath here for more information.

This is a typical universal cover problem which can be solved using Knuth dancing links' algorithm:

def has_claw_decomposition(G, certificate=False):
    import itertools
    from sage.combinat.matrices.dancing_links import dlx_solver

    id_to_edge = [frozenset(edge) for edge in G.edges(labels=False)]
    edge_to_id = {edge:i for (i,edge) in enumerate(id_to_edge)}

    rows = []

    id_to_edge = [frozenset(edge) for edge in G.edges(labels=False)]
    edge_to_id = {edge:i for (i,edge) in enumerate(id_to_edge)}
[]    
    for u in G:
        u_neighbors = G.neighbors(u)
         for three_neighbors in itertools.combinations(u_neighbors, 3):
            L = [edge_to_id[frozenset((u,v))] for v in three_neighbors]
            L.sort()
            rows.append(L)
     d = dlx_solver(rows)

    solution = d.one_solution()
    has_solution = not solution is None
     if not certificate:
        return has_solution
    else:
        if has_solution:
            solution_vertices = [[tuple(id_to_edge[id]) for id in rows[row_number]]
                                 for row_number in solution]
            return (has_solution, solution_vertices)
        else:
            return (has_solution, solution)

The first graph:

sage: from slabbe.graph import has_claw_decomposition
sage: G1 = Graph( [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3),
....: (1, 5), (2, 3), (2, 4), (3, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 8),
....: (6, 10), (7, 9), (7, 11), (8, 9), (8, 10), (9, 11), (10, 11)])
sage: has_claw_decomposition(G1)
False
sage: has_claw_decomposition(G1, certificate=True)
(False, None)

The second graph:

sage: G2 = Graph([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4),
....:    (1, 5), (2, 4), (2, 5), (3, 5), (4, 5)])
sage: has_claw_decomposition(G2)
True
sage: has_claw_decomposition(G2, certificate=True)     # random
(True,
 [[(0, 1), (1, 2), (1, 5)],
  [(0, 3), (1, 3), (3, 5)],
  [(0, 2), (2, 4), (2, 5)],
  [(0, 4), (1, 4), (4, 5)]])

Actually, I wrote the code as a new function inside the graph module of my package. It could move up to sage if it is desirable, perhaps once it is generalized to any subgraph, for instance using the graph method subgraph_search_iterator().

Note that dancing links allows to enumerate/count all solutions. Also, there is a method to solve the dlx using sat solvers or milp solvers. See the documentation of dlx solver in sagemath here for more information.