Physics of Information and Quantum Technologies Group
  • Research
  • Team
  • Publications
  • Projects
  • Meetings
  • Education
  • Positions
  • Support
  • News
  • Contact

Physics of Information Seminar

Organizers: Yasser Omar, João Seixas, Vítor R. Vieira

Complexity of Covering Problems on Hypergraphs

14/10/2016

 
Bruno Coutinho (Instituto de Telecomunicações)

Abstract:

A hypergraph is a natural generalization of a graph, where an edge (often called hyperedge) can simultaneously connect any number of vertices. The fact that hyperedges can connect more than two vertices facilitates a more faithful representation of many real-world networks. For example, given a set of proteins and a set of protein complexes, the corresponding hypergraph naturally captures the information on proteins that interact together within a protein complex. For a biochemical reaction system, the hypergraph representation indicates which biomolecules participate in a particular reaction. Collaboration networks can also be  represented by a hypergraph, where vertices represent individuals and hyperedges connect individuals who were involved in a specific collaboration, e.g. a scientific paper, a patent, a consulting task, or an art performance.

The core of a graph - defined as the remainder of the greedy leaf removal  procedure where leaves (vertices of degree one) and their neighbors are removed iteratively from the graph - has been related to the conductor-insulator transition, structural controllability, and many combinatorial optimization problems. In fact, the size of the core is related to a fundamental combinatorial issue: the computational complexity of the minimum vertex cover (MVC) problem. The MVC aims to find the smallest set of vertices in a graph (or hypergraph)  so that every edge (or hyperedge) is incident to at least one node in the set.

I will talk about two generalizations of the core in graphs to hypergraphs, one associated with the edge-cover problem and another associated with the vertex-cover problem. We found that these two cores tend to be very small in real-world hypergraphs. This result indicates that the hyperedge and vertex cover problems in real-world hypergraphs can actually be solved in polynomial time.

* * * * *

Date & time: 21/10/2016 at 16:00.

Location: Room P3.10, Mathematics Building, Instituto Superior Técnico, Lisbon.

Comments are closed.

    Mailing list

    Subscribe to the seminars/QT@IST mailing list.

    Support

    FCT, FEDER and EU FP7, namely via DP-PMI, PEst-OE/EEI/LA0008/2013, UID/EEA/50008/2013, QuSim, ProQuNet, CQVibes and PAPETS.

    Archives

    July 2018
    October 2017
    October 2016
    April 2016
    July 2015
    June 2015
    May 2015
    April 2015
    March 2015
    February 2015
    December 2014
    June 2014
    April 2014
    February 2014
    January 2014
    December 2013
    September 2013

    RSS Feed