**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Manuel Francesco Aprile

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Courses taught by this person

No results

Related research domains (7)

Combinatorics

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many

Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is,

Combinatorial optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or ca

Related publications (12)

Loading

Loading

Loading

Related units (2)

People doing similar research (122)

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst-case analysis of a random attack. We can choose a fixed number of individuals for protection, and a nonprotected target node immediately destroys all reachable nodes. The goal is to minimize the expected number of destroyed nodes in the network. In this paper, we address the GFP by several approaches: metaheuristics, approximation algorithms, polytime methods for specific instances, and exact methods for small instances. The computational complexity of the GFP is included in our analysis, where we formally prove that the corresponding decision version of the problem is NP-complete. Furthermore, a strong inapproximability result holds: there is no polynomial approximation algorithm with factor lower than 5/3, unless P=NP. This promotes the study of specific instances of the problem for tractability and/or exact methods in exponential time. As a synthesis, we propose new vulnerability/connectivity metrics and an interplay with game theory using a closely related combinatorial problem called component order connectivity.

Manuel Francesco Aprile, Yuri Faenza

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the extended formulation also depends on the number of rows of the slack matrix (hence, of the exact description in the original space). We give general sufficient conditions under which those tools can be implemented as to be output-efficient, showing applications to e.g. Yannakakis' extended formulation for the stable set polytope of perfect graphs, for which, to the best of our knowledge, an efficient construction was previously not known. For specific classes of polytopes, we give also a direct, efficient construction of those extended formulations. Finally, we deal with extended formulations coming from certain unambiguous non-deterministic protocols.