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
AbouEisha H
(2016)
Upper Domination: towards a dichotomy through boundary properties
AbouEisha H
(2016)
Combinatorial Algorithms
AbouEisha H
(2017)
Upper Domination: Towards a Dichotomy Through Boundary Properties
in Algorithmica
AbouEisha H
(2014)
Combinatorial Optimization and Applications
Alecu B
(2018)
Combinatorial Algorithms
Atminas A
(2016)
On forbidden induced subgraphs for unit disk graphs
Atminas A
(2014)
Deciding the Bell number for hereditary graph properties
Atminas A
(2016)
Deciding the Bell Number for Hereditary Graph Properties
in SIAM Journal on Discrete Mathematics
Atminas A
(2019)
Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
in Journal of Combinatorics
Atminas A
(2018)
On Forbidden Induced Subgraphs for Unit Disk Graphs
in Discrete & Computational Geometry
Atminas A
(2017)
WQO is decidable for factorial languages
in Information and Computation
Atminas Aistis
(2015)
Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique
in ELECTRONIC JOURNAL OF COMBINATORICS
Blanché A
(2017)
Clique-Width for Graph Classes Closed under Complementation
Blanché A
(2020)
Clique-Width for Graph Classes Closed under Complementation
in SIAM Journal on Discrete Mathematics
Blanché A.
(2017)
Clique-width for graph classes closed under complementation
in Leibniz International Proceedings in Informatics, LIPIcs
Cardoso D
(2016)
Efficient domination through eigenvalues
in Discrete Applied Mathematics
Collins A
(2018)
Infinitely many minimal classes of graphs of unbounded clique-width
in Discrete Applied Mathematics
Collins A
(2017)
Infinitely many minimal classes of graphs of unbounded clique-width
Collins A
(2017)
New results on word-representable graphs
in Discrete Applied Mathematics
Dabrowski K
(2017)
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
in Order
Dabrowski K
(2017)
Graph-Theoretic Concepts in Computer Science
Dabrowski K
(2014)
Combinatorics and algorithms for augmenting graphs
Dabrowski K
(2016)
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
Dabrowski K
(2020)
Clique-width and well-quasi-ordering of triangle-free graph classes
in Journal of Computer and System Sciences
Dabrowski K
(2017)
Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes
Dabrowski K
(2016)
Combinatorial Algorithms
Dabrowski K
(2015)
Combinatorics and Algorithms for Augmenting Graphs
in Graphs and Combinatorics
Hertz A
(2017)
Dominating induced matchings in graphs containing no long claw
in Journal of Graph Theory
Lozin V
(2015)
On the maximum independent set problem in subclasses of subcubic graphs
in Journal of Discrete Algorithms
Lozin V
(2017)
From matchings to independent sets
in Discrete Applied Mathematics
Lozin V
(2018)
Well-quasi-ordering versus clique-width
in Journal of Combinatorial Theory, Series B
Lozin V
(2017)
The structure and the number of P7-free bipartite graphs
in Electronic Notes in Discrete Mathematics
Lozin V
(2017)
Vertex coloring of graphs with few obstructions
in Discrete Applied 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 |