We show how to solve a maximum clique problem on a given graph by an equivalent problem on an auxiliary graph. The transformation has interesting consequences in the bilevel setting. In fact, it allows to map a clique interdiction problem with edge interdiction into a clique interdiction problem with node interdiction. As a byproduct of the mapping, we can generalize to the edge interdiction problem complexity and algorithmic results that hold for the node interdiction problem.
Reformulations and complexity of the clique interdiction problem by graph mapping
Mattia S.
Primo
2024
Abstract
We show how to solve a maximum clique problem on a given graph by an equivalent problem on an auxiliary graph. The transformation has interesting consequences in the bilevel setting. In fact, it allows to map a clique interdiction problem with edge interdiction into a clique interdiction problem with node interdiction. As a byproduct of the mapping, we can generalize to the edge interdiction problem complexity and algorithmic results that hold for the node interdiction problem.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
CI-DAM4_AAM.pdf
solo utenti autorizzati
Descrizione: AAM
Tipologia:
Documento in Pre-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
200.94 kB
Formato
Adobe PDF
|
200.94 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
