Connected and Disconnected Matchings

• Ano de defesa: 2022
• Autor(a) principal: Masquio, Bruno Porto
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; Brasil; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Algorithms; Complexity; Matching; Chordal graphs; Disconnected Matching; Connected Matching; Grafos - Teoria; Algoritmos; Complexidade; Emparelhamento; Grafos bipartidos; Grafos cordais; Emparelhamento Desconexo; Emparelhamento Conexo; Bipartite graphs; CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/20424

Problemas de emparelhamentos em grafos vêm sendo estudados há muito tempo, tendo importantes resultados tanto teóricos quanto práticos. Ao longo das décadas, variações de problemas de emparelhamentos foram estudadas. Algumas dessas podem ser resolvidas em tempo polinomial, enquanto outras não, a menos que P = NP. Nesta tese, apresentamos brevemente a história dos emparelhamentos e algumas de suas variações, juntamente com seu estado da arte. Também apresentamos resultados em uma dessas variações: P-emparelhamentos. Um emparelhamento M é um P-emparelhamento se o subgrafo induzido pelas extremidades das arestas de M satisfaz a propriedade P. Como exemplos, para escolhas apropriadas de P, os problemas Emparelhamento Induzido, Emparelhamento Unicamente Restrito, Emparelhamento Acíclico, Emparelhamento Conexo e Emparelhamento Desconexo surgem. Para muitos desses problemas, sabe-se que encontrar um P-emparelhamento de cardinalidade máxima é um problema NP-difícil. Duas exceções, que são foco desta tese, são emparelhamentos conexos e emparelhamentos desconexos, em que a propriedade P é que o subgrafo induzido pelo emparelhamento seja conexo ou desconexo, respectivamente. Enquanto podemos obter um emparelhamento conexo máximo em tempo polinomial, a complexidade de encontrar um emparelhamento desconexo máximo ainda era desconhecida, apesar de perguntada em 2005 por Goddard, Hedetniemi, Hedetniemi e Laskar [Generalized subgraph-restricted matchings in graphs, Discrete Mathematics, 293 (2005) 129 – 138]. Nesta tese, respondemos essa pergunta. De fato, consideramos o problema de forma generalizada, em que deseja-se encontrar c-emparelhamentos desconexos; para tais emparelhamentos, os subgrafos induzidos pelos seus conjuntos de vértices devem possuir pelo menos c componentes conexas. Mostramos que, para todo c ≥ 2 fixo, esse problema é NP-completo mesmo se restringirmos a entrada para grafos bipartidos de diâmetro limitado, enquanto que pode ser resolvido em tempo polinomial para c = 1. Para o caso em que c é parte da entrada, mostramos que o problema é NP-completo para grafos cordais e grafos com grau limitado, podendo ser resolvido em tempo polinomial para grafos de intervalo. Exploramos, também, a complexidade parametrizada do problema. Apresentamos um algoritmo FPT para o parâmetro treewidth e um algoritmo XP para grafos com um número polinomial de separadores minimais quando parametrizado por c. Complementamos esses resultados mostrando que, a menos que NP ⊆ coNP=poly, o problema relacionado Emparelhamento Induzido não admite kernel polinomial quando parametrizado pela cobertura de vértices e pelo tamanho do emparelhamento, nem quando parametrizamos pela distância para clique e tamanho do emparelhamento. Para emparelhamentos conexos, apresentamos um algoritmo de tempo linear para encontrar emparelhamentos conexos máximos e um emparelhamento máximo é dado na entrada. Então, voltamos nossa atenção para uma generalização de emparelhamentos conexos que considera grafos ponderados em arestas e cujo problema chamamos de Emparelhamento Conexo Ponderado Máximo. Esse problema foi motivado pelo problema clássico Emparelhamento Ponderado Máximo, estudado há décadas, e com várias aplicações, incluindo o problema bem conhecido Atribuição. Além disso, alguns outros P-emparelhamentos, tais como acíclicos e induzidos, também já foram considerados para grafos ponderados. No Emparelhamento Conexo Ponderado Máximo, queremos encontrar um emparelhamento M tal que as extremidades das suas arestas induzem um subgrafo conexo e a soma dos pesos das arestas de M é máxima. Ao contrário do problema não ponderado Emparelhamento Conexo, que pode ser resolvido em tempo polinomial para grafos gerais, mostramos que Emparelhamento Conexo Ponderado Máximo é NP-difícil mesmo para grafos bipartidos de diâmetro limitado, grafos starlike, grafos planares bipartidos e grafos subcúbicos planares, enquanto pode ser resolvido em tempo linear para árvores e grafos com grau máximo dois. Quando restringimos as arestas para terem pesos somente não negativos, mostramos que o problema pode ser resolvido em tempo polinomial para grafos cordais, enquanto que continua NP-difícil para a maior parte dos casos. Também estudamos a complexidade parametrizada do Emparelhamento Conexo Ponderado Máximo. Como resultados positivos, apresentamos um algoritmo de tempo exponencial parametrizado pela treewidth. Em relação a kernelização, mostramos que, quando restringimos os pesos a valores binários, o seu problema de decisão, Emparelhamento Conexo Ponderado, não admite kernel polinomial quando parametrizado pelo tamanho da cobertura de vértices sob hipóteses teóricas de complexidade padrão.