Stability in graphs: methodologies and related problems
Lead Research Organisation:
University of Warwick
Department Name: Mathematics
Abstract
In 1965, Edmonds published his celebrated solution to the maximum matching problem, which is a special case of the maximum independent (stable) set problem restricted to the class of line graphs. Two key tools in the solution of Edmonds are augmenting chains and cycle shrinking. Both tools can be extended to general graphs but neither of them has been studied or used on a systematic basis. The idea of the present project is to lay theoretical foundations for both techniques (augmenting graphs and graph transformations) in order to turn their isolated applications into a developed methodology and apply this methodology to obtain faster exponential time algorithms for the maximum independent set and related problems, such as satisfiability and constraint satisfaction.
Planned Impact
We expect that the proposal will have impact of different types and that the impact will be felt by beneficiaries from various groups.
In terms of groups of beneficiaries:
1. The first and immediate beneficiaries of the project will be people working in Graph Theory, as most results will be obtained and described by means of graph theory.
2. The algorithmic community will benefit through a new methodology based on total struction, which has no analogues.
3. Our results will also bring new blood to the development of SAT and CSP solvers.
Since maximum independent set and closely related problems, such as maximum clique, find applications far beyond Discrete Mathematics and Theoretical Computer Science, in areas such as Patter Recognition, Data Mining, etc., we also believe that our results will be beneficial in those areas too.
In terms of types of the impact:
1. We will make a significant contribution to knowledge, including both scientific advances and technology, just by achieving the objectives stated in the case for support.
2. We will recruit two young researchers and will transfer our skills to the next generation of researchers ensuring the people pipeline.
3. We will make significant long run contributions to Society and Economy by implementing our theoretical findings in a new generation software for Automated Reasoning. In the long run, this will lead to a better quality of life and to wealth creation.
In terms of groups of beneficiaries:
1. The first and immediate beneficiaries of the project will be people working in Graph Theory, as most results will be obtained and described by means of graph theory.
2. The algorithmic community will benefit through a new methodology based on total struction, which has no analogues.
3. Our results will also bring new blood to the development of SAT and CSP solvers.
Since maximum independent set and closely related problems, such as maximum clique, find applications far beyond Discrete Mathematics and Theoretical Computer Science, in areas such as Patter Recognition, Data Mining, etc., we also believe that our results will be beneficial in those areas too.
In terms of types of the impact:
1. We will make a significant contribution to knowledge, including both scientific advances and technology, just by achieving the objectives stated in the case for support.
2. We will recruit two young researchers and will transfer our skills to the next generation of researchers ensuring the people pipeline.
3. We will make significant long run contributions to Society and Economy by implementing our theoretical findings in a new generation software for Automated Reasoning. In the long run, this will lead to a better quality of life and to wealth creation.
Organisations
People |
ORCID iD |
Vadim Lozin (Principal Investigator) | |
Igor Razgon (Co-Investigator) |
Publications
Atminas A
(2017)
WQO is decidable for factorial languages
in Information and Computation
Dabrowski K
(2016)
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
Dabrowski K
(2017)
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
in Order
Lozin V
(2018)
Well-quasi-ordering versus clique-width
in Journal of Combinatorial Theory, Series B
Atminas Aistis
(2015)
Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique
in ELECTRONIC JOURNAL OF COMBINATORICS
Lozin V
(2017)
Vertex coloring of graphs with few obstructions
in Discrete Applied Mathematics
AbouEisha H
(2017)
Upper Domination: Towards a Dichotomy Through Boundary Properties
in Algorithmica
AbouEisha H
(2016)
Upper Domination: towards a dichotomy through boundary properties
Lozin V
(2017)
The structure and the number of P7-free bipartite graphs
in Electronic Notes in Discrete Mathematics
Lozin V
(2017)
The structure and the number of P 7 -free bipartite graphs
in European Journal of Combinatorics
Description | (1) The set of all minimal infinite classes of augmenting graphs has been completely characterized. (2) The first polynomial-time algorithm for the maximum independent set problem in the class of sub-cubic graphs excluding a tripod S222 has been developed. (3) It has been shown that well-quasi-ordering is decidable for factorial languages.(4) New boundary classes have been discovered for the upper dominating set problem. |
Exploitation Route | Finding (1) may lead to better solutions for the maximum independent set problem. Finding (2) makes a breakthrough step towards the characterization of the boundary separating difficult instances of the maximum independent set problem from polynomially solvable ones. |
Sectors | Digital/Communication/Information Technologies (including Software),Education |
URL | http://link.springer.com/article/10.1007%2Fs00373-015-1660-0 |