Sometimes, under certain circumstances, we know that problems that are in general hard to solve become easy for certain input instances. Of course, we have to be able to recognize such "lucky instances"and therefore we have to be able to characterize their "lucky properties" and exploit the characterization to devise efficient recognition algorithms. In other words we have to be able to answer the following question efficiently: "Is this instance a lucky one"; if the answer is yes then we are lucky as well because we are done: since the problem can be easily solved just solve it. If the answer is no.. well, in this case we are not lucky and we have to try other ways. We can legitimately complain and regret for the bad luck nonetheless we cannot regret for the time lost for having misunderstood the complexity of the problem. In a recent work [Nicola Apollonio, Anna Galluccio. Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths. SIAM J. Discrete Math. 29(4): 1837-1863 (2015)] we characterized a special class of "balanced graphs" ("balanced diamond-free graphs"), namely a class of lucky instances for many interesting linear integerprogramming problems. Let us try to understand the meaning of the previous mysterious sentences. Consider a community of people (e.g. asocial network). Suppose you have a sheet of paper large enough to write down the name of each member of the community. Draw now a line, no matter its shape, joining two members of the community if they know each other. Well, the picture we get in this way is a representation of a mathematical object known as "graph". Clearly, by changing the entities, graphs can be used to model a great variety of relationships while the mathematics behind is always the same. Let us look a bit more inside our graph. Let us suppose to be interested in those members whose age is, say, under thirty (or to those whose citizenship is Italian or even to those that usually drink a specific juice and so forth). We can then form a subnetwork by deleting from our drawing all the other members and by keeping only those we are interested in along with lines connecting them. What we get in this way is the representation of an "induced subgraph" of the original graph. Moreover, among the members of the community there can be subcommunities, namely sets of members who pairwise know each other within the set and such that any other member outside fails to know at least one member inside. Well any such a subcommunity is known as a "maximal clique" of the graph. Let us try to understand what is a "balanced graph". Let us suppose that we can offer two kinds of services to the members of the social network (say, free access to two different textbooks---what a delicious gift for the network..) in such a way that: 1) no subcommunity is offered exactly one type of service (unless the subcommunity reduces to a single member) and 2) the latter property holds for every subnetwork; well, in this case we say that the network is balanced. Finally, suppose we want to select members from the social network and to make them responsible, in some respects, for the subcommunities they belong to (for instance, they have to collect comments on the two textbooks) in such a way that each subcommunity in the network has at least one responsible. The latter set of responsible members is called a "clique transversal" of the graph. Well, if the network is balanced, we know from the mathematics of combinatorial optimization that the problem of finding a clique transversal with the least possible number of members is easy while it is difficult in general. So what is left is just to answer the question "is your social network a balanced one?". Under some further restrictions on the graph, by investigating the combinatorics of certain words (stings of letters) known as Dyck words, we could answer the latter question.
Focus