Classes máximas para qual maior conjunto independente pode ser encontrado em tempo polinomial?

28

O ISGCI lista mais de 1100 classes de gráficos. Para muitos deles, sabemos se INDEPENDENT SET pode ser decidido em tempo polinomial; às vezes são chamadas de classes fáceis de IS . Gostaria de compilar uma lista de classes máximas fáceis de IS. Essas classes juntas formam o limite de tratabilidade (conhecida) para esse problema.

Como é possível adicionar apenas um número finito de gráficos a qualquer classe infinita fácil de IS sem afetar a capacidade de rastreamento, algumas restrições estão em ordem. Vamos restringir as classes àquelas que são hereditárias (fechadas em subgráficos induzidos, ou equivalentemente, definidos por um conjunto de subgráficos induzidos excluídos). Além disso, vamos considerar apenas as famílias que são livres de X para um conjunto X com uma pequena descrição. Não pode são também ser correntes ascendentes infinitos de classes de tratáveis (tais como (P,Estrela1,2,k)-free e as classes descritas por David Eppstein abaixo), mas vamos restringir a atenção às classes que realmente provaram ser fácil.

Aqui estão os que eu conheço:

Outras classes máximas são conhecidas?


Edit: Veja também uma pergunta relacionada feita por Yaroslav Bulatov que lida com classes definidas por menores excluídos. O que é fácil para gráficos com exclusão menor? e veja Propriedades globais de classes hereditárias? para uma pergunta mais geral, perguntei anteriormente sobre classes hereditárias.

Como Jukka Suomela aponta nos comentários, o caso dos menores excluídos também é interessante (e faria uma pergunta interessante), mas esse não é o foco aqui.

Para evitar o exemplo de David, uma classe máxima também deve ser definida como os gráficos sem X, onde nem todo gráfico em X possui um vértice independente.

Classes dadas nas respostas abaixo:


Adicionado em 09/10/2013: o resultado recente de Lokshtanov, Vatshelle e Villanger, mencionado por Martin Vatshelle em uma resposta, substitui algumas das classes máximas conhecidas anteriormente.

Em particular, estar livre de IS-fácil subsumes ( P 5 , grilo) -livre, ( P 5 , K n , n ) -livre, ( P 5 , X 82 , X 83 ) -livre, e ( P 5 , casa) -free todos sendo fácil.P5P5P5Kn,nP5X82X83P5

Isso significa que todas as classes de gráfico hereditárias definidas por um único subgrafo induzido proibido com até cinco vértices podem agora ser definitivamente classificadas como IS-easy ou não-IS-easy.

Infelizmente a prova de que gráficos Livres de formar uma IS-fácil classe não parece trabalho para P 6 Livre de gráficos, de modo a próxima fronteira é classificar todas as classes gráfico hereditários definidas por um único gráfico de seis vértice.P5P6

Continuo especialmente interessado em IS-fáceis classes da forma -livre por alguma coleção X de gráficos com infinitamente muitas classes de isomorfismo, mas onde Y -livre não é IS-fácil para qualquer Y X .XXYYX

András Salamon
fonte
1
E os gráficos com largura de árvore limitada? Eu acho que eles já estão contidos em uma das classes que você mencionou?
Jukka Suomela 27/10/10
@Jukka: até onde eu sei, a largura da árvore limitada não é possível capturar com um pequeno conjunto de subgráficos induzidos excluídos. Por exemplo, treewidth 2 é -minor-livre; isso gera um conjunto infinito de subgráficos induzidos excluídos. Por outro lado, "k-tree parcial" pode se qualificar como uma descrição "pequena". O que você acha? K4
András Salamon
ás: Oh, parece que eu não tinha lido sua pergunta com bastante atenção, pensei que você também estivesse interessado em famílias de gráficos que são caracterizadas em termos de menores proibidos.
Jukka Suomela 27/10/10
Faz qualifica -free? Como existem apenas POUCOS conjuntos independentes (precisamente, O ( n 2 ) ) nesses gráficos. 2K2O(n2)
Hsien-Chih Chang #
@ Hsien-Chih Chang: Obrigado por mencionar a classe Balas-Yu, tinha esquecido disso. Sim, isso certamente daria uma resposta relevante.
András Salamon

Respostas:

10

A questão já é um pouco mais antiga, mas o ISGCI pode ser de alguma ajuda aqui.

Quando você inicia o aplicativo Java ISGCI e acessa o menu Problemas -> Limite / Classes abertas -> Conjunto independente, é exibida uma caixa de diálogo com 3 listas.

A lista P Máximo contém todas as classes C (no ISGCI) nas quais o IS pode ser resolvido em tempo polinomial, de modo que exista uma superclasse mínima de C na qual o IS não seja conhecido em P (ou seja, NP-completo, aberto ou desconhecido para ISGCI). Selecionar uma classe e clicar em 'Draw' desenhará a classe e as superclasses encontradas ao subir o estilo BFS na hierarquia de inclusão, na medida do necessário para encontrar uma classe na qual o IS não é conhecido como P.

A lista Minimal NP-complete é inversa: contém classes nas quais IS é NP-complete, de modo que nem todas as subclasses máximas também sejam NP-complete. O desenho fica na hierarquia até que uma classe não-NP-completa seja encontrada.

A lista aberta contém classes para as quais o problema é aberto ou desconhecido. O desenho percorre as super / subclasses até que uma classe seja alcançada e não esteja aberta.

Ao criar um desenho, é uma boa ideia definir a coloração para o problema Conjunto Independente (Problemas -> Cor para o problema -> Conjunto independente).


Com relação à pergunta de Standa Zivny, as 20 classes a seguir estão listadas no ISGCI com complexidade conhecida para o problema de IS não ponderado, mas com complexidade desconhecida para o caso ponderado (o ISGCI não pode distinguir entre algoritmos polinomiais "simples" e "complicados"):

gc_11 estendido P 4 -laden
gc_128 EPT
gc_415 bem coberto
gc_428 (K 3,3 -e, P 5 , X 98 ) -livre
gc_648 (K 3,3 -e, P 5 ) -livre
gc_752 co-hereditária clique-Helly
gc_756 (E, P) -livre
gc_757 (P, T 2 ) -livre
gc_758 (P, P 8 ) -livre
gc_759 (K 3,3 -e, P 5 , X 99 ) -livre
gc_808 (C 6 , K 3, 3 + e, P, P 7 , X 37 , X 41 ) -livre
gc_811 (P, estrela1,2,5 ) sem
gc_812 (P 5 , P 2 ∪ P 3 ) sem
gc_813 (P, P 7 ) sem
gc_818 (P, estrela 1,2,3 ) sem
gc_819 (P, estrela 1, 2,4 ) sem
gc_841 (2K 3 + e, A, C 6 , E, K 3,3 -e, P 6 166 , X 167 , X 167 , X 169 , X 170 , X 171 , X 172 , X 18 , X 45 , X 5 , X 58 , X 84 , X 95 , X, R, X 98 , A, C 6 , E, P 6 , R, X 166 , X 167 , X 169 , X 170 , X 171 , X 172 , X 18 , X 45 , X 5 , X 58 , X 84 , X 95 , X 98 , antena, co-antena, co-dominó, co-fish, co-twin-house, dominó, fish, twin-house) - livre
gc_894 co-circular perfeito
gc_895 fortemente circular perfeito
(3K 2 , E, P 2 4 P 4 , líquido) livre

Sem dúvida, vários deles também terão algoritmos conhecidos para o caso ponderado. Adições e correções são sempre bem-vindas no endereço indicado na página da ISGCI!

Ernst de Ridder
fonte
obrigado pelo ponteiro para a funcionalidade do aplicativo Java para encontrar classes máximas tratáveis ​​e a lista de classes para as quais a caixa ponderada está aberta. E, claro, obrigado pelo seu trabalho em ISGCI!
András Salamon 02/02
12

Um artigo interessante para analisar pode ser:

A. Brandstadt, VV Lozin, R. Mosca: Conjuntos Independentes de Peso Máximo em Gráficos Livres de Maçã, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. doi: 10.1137 / 090750822

A classe infinita de maçãs é definida como ciclos C_k, k> = 5, cada um com uma haste.

Você não menciona se sua noção de facilidade de IS inclui o problema de IS ponderado. Os gráficos sem cadeira (também conhecidos como gráficos sem garfo) são conhecidos por serem fáceis de IS:

VE Alekseev, algoritmo polinomial para encontrar os maiores conjuntos independentes em gráficos sem garfos, Discrete Applied Mathematics 135 (1-3) (2004) 3–16. doi: 10.1016 / S0166-218X (02) 00290-1

A tratabilidade do caso ponderado é uma extensão não trivial, consulte:

VV Lozin, M. Milanic: Um algoritmo polinomial para encontrar um conjunto independente de peso máximo em um gráfico sem garfo, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi: 10.1016 / j.jda.2008.04.001

Existem outras classes (interessantes) em que o problema de IS ponderado é significativamente mais difícil / intratável / aberto do que o caso não ponderado?

Standa Zivny
fonte
1
Pergunta interessante, pode valer a pena ser postada separadamente.
András Salamon
Na definição de maçãs, você quer dizer k ≥ 4, certo?
David Eppstein
Sim, k> = 4, desculpe pelo erro de digitação.
Standa Zivny
10

De acordo com Vassilis Giakoumakis e Irena Rusu, Disc. Appl. Matemática. 1997 , os gráficos livres de (P5, casa) (também conhecidos como gráficos livres de (P5, coP5)) são fáceis de IS.

Outro, creditado pelo ISGCI a V. Lozin, R. Mosca Disc. Appl. Matemática. 2005 , é a família de gráficos livres de (K2 u garra) .

Também pode haver infinitas cadeias ascendentes de classes tratáveis

Definitivamente, existem infinitas cadeias ascendentes. Se H é um conjunto finito de gráficos para os quais os gráficos livres de H são fáceis de IS, sejam H os gráficos formados adicionando um vértice independente a cada gráfico em H. Então, os gráficos livres de H também são fáceis de IS: basta aplicar o algoritmo sem H aos conjuntos de não vizinhos de cada vértice. Por exemplo, como o ISGCI descreve, os gráficos sem co-gema são fáceis de IS, pelo motivo de que uma co-gema é um P4 mais um vértice independente e os gráficos sem P4 são fáceis de IS. Portanto, você provavelmente deseja restringir sua pergunta a classes máximas nas quais nem todos os subgráficos proibidos possuem um vértice independente.

David Eppstein
fonte
Obrigado pelas aulas adicionais e por destacar uma construção fácil de cadeias infinitas! Será reformulado.
András Salamon
Assim também os gráficos sem garras, conforme a entrada da Wikipedia no conjunto Independente: en.wikipedia.org/wiki/…
gphilip
3
@ gphilip: livre de garras estão incluídas tanto sem cadeira quanto sem garras (K2 u).
David Eppstein
8

Um artigo aceito na SODA 2014 fornece um algoritmo de tempo polinomial para o Max Weight Independent definido em P5gráficos gratuitos. http://www.ii.uib.no/~martinv/Papers/ISinP5free.pdf

Seja H um gráfico com no máximo 5 vértices, a complexidade do conjunto Independente é conhecida na classe de gráficos sem H.

O problema é difícil se H contiver um ciclo ou um vértice de grau 4. Os únicos casos restantes de H conectado sãoP5, garra e garfo, para essas classes o problema é polinomial para o H desconectado sem ciclos, existem apenas algumas possibilidades. Se H tiver vértices isolados, é fácil ver que IS é polinomial, pois é polinomial para todo H em 4 vértices sem ciclos. O casoH=P2P3 foi estabelecida por Lozin e Mosca em 2005.

Martin Vatshelle
fonte