Path partitions and stable sets in digraphs

• Grant number: 17/21345-7
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: April 01, 2018
• End date: 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

Abstract

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)

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., 2019-08-30. (17/21345-7, 17/23623-4, 15/11937-9)