International audience

The Median String Problem calls for finding a string that minimizes the average distance from a given set of strings. Under the Levenshtein (or edit) metric, the problem is NP-hard even for binary strings. We devised two novel integer linear programming models for this case and tested them against the only formulation we are aware of in the literature. Our numerical experiments attest to the efficacy of the proposed approach.

In this paper, we introduce a family of valid inequalities for the strongest currently known integer programming formulation of treewidth based on perfect elimination orderings. These inequalities arise from the structure of induced chordless cycles (holes) and strengthen the canonical linear relaxation by enforcing constraints that every feasible chordal completion must satisfy. To handle the exponentially many such inequalities, we develop a dedicated separation routine capable of detecting violated k-hole constraints within a cutting-plane framework. Our computational results show that incorporating these inequalities substantially improves the quality of the lower bounds across a broad range of graph classes, in some cases nearly closing the integrality gap.

We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ε, for some given ε ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1+ε)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1+ε)-approximate price of anarchy, i.e., the price of anarchy of (1+ε)-approximate pure Nash equilibria, is at least (k-1)/((k-1)ε +k), and that this bound is tight for any ε ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ε)-approximate one-round walk starting from any initial strategy profile, where a (1 + ε)-approximate one-round walk is a sequence of (1 + ε)-approximate best-responses, one for each player. We provide a lower bound of min{(k-2)/k, (k-1)/((k-1)ε+k)} on this ratio, for any ε ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ε. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2.

The graph edit distance (GED) is among the most widely used graph similarity measures in practice. It asks for a minimum cost edit path between two given labeled graphs G and H , where the edit path is defined as a sequence of operations (e.g., node and edge insertions, deletions or substitutions) that successively transform the graph G into H. In this work, we suggest a new ILP formulation (FORI) based on orienting the corresponding edge variables. Moreover, we suggest enhancing two state-of-the-art ILP formulations by incorporating additional inequalities. We theoretically compare the strength of the formulations with respect to their Linear Programming relaxations. The result is a hierarchy with (FORI) at the top. Our extensive evaluation on widely used benchmark sets shows that our improved formulations run significantly faster than the previous ones. These allow to solve to proven optimality all the reference instances from common databases, such as the IAM Graph Database, many of which were prohibitive with state-of-the-art methods. Moreover, we are able to compute the GED of a small pattern and a large graph such as CORA and PUBMED, having up to 19,717 nodes and 44,327 edges.

The k -shortest simple paths problem asks to compute a set of top- k shortest simple paths from a source to a sink in a graph G = ( V , E ) with | V | = n vertices and | E | = m edges. The most well-known algorithm for solving this problem is due to Yen (1971) with time complexity in O ( k n ( m + n log ⁡ n ) ) and the fastest algorithm is due to Gotthilf and Lewenstein (2009) with time complexity in O ( k n ( m + n log ⁡ log ⁡ n ) ) . For bounded treewidth graphs, Eppstein and Kurz (2017) lowered the computational complexity to O ( k n ) by retrieving paths from the k smallest solutions of a monadic second-order formula, and to O ( n + k log ⁡ ( n ) ) to retrieve the k shortest simple distances only. In this paper, we provide an algorithm that answers k -shortest simple distances in O ( k + n ) time on graphs with treewidth at most 2, and a constructive algorithm, simpler than that of Eppstein and Kurz, that solves the k -shortest simple paths problem in O ( k n ) time on bounded treewidth graphs.

A beer graph is an edge-weighted graph G = (V,E,ω) with beer vertices B ⊆ V. A beer path between two vertices s and t of a beer graph is a path that connects s and t and visits at least one vertex in B. The beer distance between two vertices is the weight of a shortest beer path, i.e. a beer path having minimum total weight. A graph indexing scheme is a two-phase method that constructs an index data structure by a one-time preprocessing of an input graph and then exploits it to compute (or accelerate the computation of) answers to queries on structures of the graph dataset. In the last decade, such indexing schemes have been designed to perform, effectively, many relevant types of queries, e.g. on reachability, and have gained significant popularity in essentially all data-intensive application domains where large number of queries have to be routinely answered (e.g. journey planners), since they have been shown, through many experimental studies, to offer extremely low query times at the price of limited preprocessing time and space overheads. In this paper, we showcase that an indexing scheme, to efficiently execute queries on beer distances or shortest beer paths for pairs of vertices of a beer graph, can be obtained by adapting the highway labeling, a recently introduced indexing method to accelerate the computation of classical shortest paths. We design a preprocessing algorithm to build a whl index, i.e. a weighted highway labeling of a beer graph, and show how it can be queried to compute beer distances and shortest beer paths. Through extensive experimentation on real networks, we empirically demonstrate its practical effectiveness and superiority, in terms of offered trade-off between preprocessing time, space overhead and query time, with respect to the state-of-the-art.

We study digraph k-coloring games where strategic agents are vertices of a digraph and arcs represent agents' mutual unidirectional conflicts/idiosyncrasies. Each agent can select, as strategy, one of k different colors, and her payoff in a given state (a k-coloring) is given by the number of outgoing neighbors with a color different from her one. Such games model lots of strategic real-world scenarios and are related to several fundamental classes of anti-coordination games. Unfortunately, the problem of understanding whether an instance of the game admits a pure Nash equilibrium (NE), i.e., a state where no agent can improve her payoff by changing strategy, is NP-complete. Thus, in this paper, we focus on algorithms to compute an approximate NE: informally, a coloring is an approximate γ-NE, for some γ ≥ 1, if no agent can improve her payoff, by changing strategy, by a multiplicative factor of γ. Our contribution is manifold and of both theoretical and experimental nature. First, we characterize the hardness of finding pure and approximate equilibria in both general and special classes of digraphs. Second, we design and analyze three approximation algorithms with different theoretical guarantees on the approximation ratio, under different conditions; (i) algorithm APPROX-1 which computes, for any k ≥ 3, a Δo-NE for any n vertex graph having a maximum outdegree of Δo, in polynomial time; (ii) algorithm LLL-SPE, a randomized algorithm that, for any constant k ≥ 2, determines a γ-NE for some constant γ but only in digraphs whose minimum outdegree is sufficiently large, in polynomial time in expectation; (iii) algorithm APPROX-3 which, for any ε, computes a (1+ε)-NE by using O(log(n)/ε) colors, for any n-vertex digraph. Note that, the latter shows that a (1+ε)-NE exists and can be computed in polynomial time for k = O(log(n)). Finally, to assess how proposed algorithms behave in the typical case, we complete our study with an extensive experimental evaluation showing that, while newly introduced algorithms achieve bounded worst case behavior, they generally perform poorly in practice. Motivated by such unsatisfactory performance, we shift our attention to the best-response paradigm, successfully applied to other classes of games, and design and experimentally evaluate it a heuristic based on such paradigm. Our experiments provide strong evidences of such approach outperforming, in terms of approximation and computational time, all other methods and hence identify it as the most suited candidate for practical usage. More remarkably, it is also able to compute exact, pure NE in the great majority of cases. This suggests that, while these games are known to not always possess a pure NE, such an equilibrium often exists and can be efficiently computed, even by a distributed uncoordinated interaction of the agents.