Minimum entropy coloring

We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy of the coloring. The minimum entropy of a coloring is called the chromatic entropy and was shown by Alon and Orlitsky (IEEE Trans. Inform. Theory 42(5):1329–1339, 1996) to play a fundamental role in the problem of coding with side information. In this paper, we consider the minimum entropy coloring problem from a computational point of view. We first prove that this problem is NP-hard on interval graphs. We then show that, for every constant ε>0, it is NP-hard to find a coloring whose entropy is within (1−ε)log n of the chromatic entropy, where n is the number of vertices of the graph. A simple polynomial case is also identified. It is known that graph entropy is a lower bound for the chromatic entropy. We prove that this bound can be arbitrarily bad, even for chordal graphs. Finally, we consider the minimum number of colors required to achieve minimum entropy and prove a Brooks-type theorem. S. Fiorini acknowledges the support from the Fonds National de la Recherche Scientifique and GERAD-HEC Montréal. G. Joret is a F.R.S.-FNRS Research Fellow.     

Conspiracies beyond Fake News. Produsing Reinformation on Presidential Elections in the Transnational Hybrid Media System

As presidential elections carry the promise of distilling the contested and elusive “will of the people,” the protracted media event intensifies the public demand for exposing the transgressions of the aspiring political elite. This expectation provides fertile ground for investigative journalism, ultrapartisan smear campaigns, fake news, and full-fledged conspiracy theories that are sometimes difficult to differentiate from one another in a hybridized media space. We compare three unique conspiracy stories—Macronleaks, Pizzagate, and Voter fraud—emerging during the previous French and American elections. We assess the divergent strategies of social action that contribute to the stories’ dissimilar patterns for intervening the political news cycle with the “reinformative toolkit” and deconstruct the common conspiratorial “masterplot” for “reinforming” the public. Focusing on online “produsers”—media users functioning as (dis)information producers—we analyze how the grassroots level participated in shaping the conspiracy stories’ synopses and channeling news-framed, conspiratory content between mainstream and “countermedia” outlets.     

The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs

The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem played on a graph representing a network. Its edges are colored either red or blue, and the red edges have a given fixed cost, representing the competitor’s prices. The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. We study this problem in the cases of planar and bounded-treewidth graphs. We show that the problem is NP-hard on planar graphs but can be solved in polynomial time on graphs of bounded treewidth.