Advanced search
Start date

Path partitions and stable sets in digraphs

Grant number: 17/21345-7
Support Opportunities:Scholarships in Brazil - Scientific Initiation
Effective date (Start): April 01, 2018
Effective date (End): June 30, 2019
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Candida Nunes da Silva
Grantee:Lucas Rigo Yoshimura
Host Institution: Centro de Ciências em Gestão e Tecnologia (CCGT). Universidade Federal de São Carlos (UFSCAR). Campus de Sorocaba. Sorocaba , SP, Brazil


The subject of this project is the relation of path partitions and stable sets in digraphs. A path partition and a stable set are\emph{orthogonal} if each path in the path partition has exactly one vertex of the stable set. In 1960, Gallai and Milgram showed that a path partition with the minimum number of paths is always orthogonal to some stable set of the digraph. Thus, the minimum number of paths needed to cover all vertices by directed paths, denoted by $\pi$, is alower bound to the size of the maximun independent set, denoted by$\alpha$. Later, in 1982, Berge proposed a conjecture which generalizes the relation observed by Gallai and Milgram. Given a positive integer $k$, Berge suggested a new notion of minimality of a path partition which depends on parameter $k$. He observed that for this new notion of minimality it seemed true that for every $k$-coloring of the vertices of the digraph covering the maximum number of colors, each color class would be orthogonal to a minimum path partition. This is, therefore, the statement of Berge's Conjecture. Gallai and Milgram's Theorem is a special case of Berge's Conjecture in which $k=1$. This research project aims at studying this celebrated conjecture of Berge, learning about all partial results known but focusing on the special case $k=1$; the most important partial result. For $k=1$ it is known that there is a polynomial time algorithm based on the proof of Gallai and Milgram's Theorem to find a minimum path partition and an independent set orthogonal to it. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
YOSHIMURA, LUCAS R.; SAMBINELLI, MAYCON; DA SILVA, CANDIDA N.; LEE, ORLANDO. Linial's Conjecture for Arc-spine Digraphs. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 12-pg., . (17/21345-7, 17/23623-4, 15/11937-9)

Please report errors in scientific publications list using this form.