Revision history [back]

This problem is best solved with integer programming. Here is my solution, which you can also run at Sagecell:

import itertools
from sage.numerical.mip import MIPSolverException

def find_claw_decomposition(G):

    # quick check
    if G.size()%3: 
        print('Size is not a multiple of 3')
        return None

    milp = MixedIntegerLinearProgram()

    # indicator variables: att[(edge,node)] = 1 iff edge is part of claw rooted at node
    att = milp.new_variable(binary=True)
    # ratios from division by 3
    rat = milp.new_variable(integer=True)

    # each edge should be attached to one of its endpoints
    for e in G.edges(labels=False):
        milp.add_constraint( att[(e,e[0])] + att[(e,e[1])] == 1 )

    # each node should have a multiple of 3 attached edges
    for v in G.vertices():
        milp.add_constraint( sum( att[(e,v)] for e in G.edges_incident(v,labels=False) ) == 3 * rat[v] )

    try:
        milp.solve()
    except MIPSolverException:
        print('No decomposition exists.')
        return None

    claws = []
    A = milp.get_values(att,convert=bool,tolerance=1e-6)

    for v in G.vertices():
        it = filter(lambda e: A[(e,v)], G.edges_incident(v,labels=False))
        while ( claw := tuple(itertools.islice(it,3)) ):
            claws.append(claw)

    return claws

This problem is best solved with integer programming. Here is my solution, which you can also run at Sagecell:

import itertools
from sage.numerical.mip import MIPSolverException

def find_claw_decomposition(G):

    # quick check
    if G.size()%3: 
        print('Size is not a multiple of 3')
        return None

    milp = MixedIntegerLinearProgram()

    # indicator variables: att[(edge,node)] = 1 iff edge is part of claw rooted at node
    att = milp.new_variable(binary=True)
    # ratios from division by 3
    rat = milp.new_variable(integer=True)

    # each edge should be attached to one of its endpoints
    for e in G.edges(labels=False):
        milp.add_constraint( att[(e,e[0])] + att[(e,e[1])] == 1 )

    # each node should have a multiple of 3 attached edges
    for v in G.vertices():
        milp.add_constraint( sum( att[(e,v)] for e in G.edges_incident(v,labels=False) ) == 3 * rat[v] )

    try:
        milp.solve()
    except MIPSolverException:
        print('No decomposition exists.')
        return None

    claws = []
    A = milp.get_values(att,convert=bool,tolerance=1e-6)

    for v in G.vertices():
        it = filter(lambda e: A[(e,v)], G.edges_incident(v,labels=False))
        while ( claw := tuple(itertools.islice(it,3)) ):
            claws.append(claw)

    return claws

For example, running on your second graph:

G = 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)])
find_claw_decomposition(G)

produces the following decomposition:

[((0, 1), (0, 2), (0, 3)),
 ((1, 2), (1, 3), (1, 5)),
 ((0, 4), (1, 4), (2, 4)),
 ((2, 5), (3, 5), (4, 5))]

This problem is best solved with integer programming. Here is my solution, which you can also run at Sagecell:

import itertools
from sage.numerical.mip import MIPSolverException

def find_claw_decomposition(G):

    # quick check
    if G.size()%3: 
        print('Size is not a multiple of 3')
        return None

    milp = MixedIntegerLinearProgram()

    # indicator variables: att[(edge,node)] = 1 iff edge is part of claw rooted at node
    att = milp.new_variable(binary=True)
    # ratios from division by 3
rat[v] = number of claws rooted at v
    rat = milp.new_variable(integer=True)

    # each edge should be attached to one of its endpoints
    for e in G.edges(labels=False):
        milp.add_constraint( att[(e,e[0])] + att[(e,e[1])] == 1 )

    # each node should have a multiple of 3 attached edges
    for v in G.vertices():
        milp.add_constraint( sum( att[(e,v)] for e in G.edges_incident(v,labels=False) ) == 3 * rat[v] )

    try:
        milp.solve()
    except MIPSolverException:
        print('No decomposition exists.')
        return None

    claws = []
    A = milp.get_values(att,convert=bool,tolerance=1e-6)

    for v in G.vertices():
        it = filter(lambda e: A[(e,v)], G.edges_incident(v,labels=False))
        while ( claw := tuple(itertools.islice(it,3)) ):
            claws.append(claw)

    return claws

For example, running on your second graph:

G = 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)])
find_claw_decomposition(G)

produces the following decomposition:

[((0, 1), (0, 2), (0, 3)),
 ((1, 2), (1, 3), (1, 5)),
 ((0, 4), (1, 4), (2, 4)),
 ((2, 5), (3, 5), (4, 5))]