  We study the problem of allocating indivisible chores to agents under the
Maximin share (MMS) fairness notion. The chores are embedded on a graph and
each bundle of chores assigned to an agent should be connected. Although there
is a simple algorithm for MMS allocations of goods on trees, it remains open
whether MMS allocations of chores on trees always exist or not, which is a
simple but annoying problem in chores allocation. In this paper, we introduce a
new method for chores allocation with connectivity constraints, called the
group-satisfied method, that can show the existence of MMS allocations of
chores on several subclasses of trees. Even these subcases are non-trivial and
our results can be considered as a significant step to the open problem. We
also consider MMS allocations of chores on cycles where we get the tight
approximation ratio for three agents. Our result was obtained via the linear
programming (LP) method, which enables us not only to compute approximate MMS
allocations but also to construct tight examples of the nonexistence of MMS
allocations without complicated combinatorial analysis. These two proposed
methods, the group-satisfied method and the LP method, have the potential to
solve more related problems.
