Given an undirected and vertex weighted graph G = (V,E,w), the Weighted Feedback Vertex Problem (WFVP) consists of finding a subset F V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The WFVP on general graphs is known to be NP-hard and to be polynomially solvable on some special classes of graphs (e.g., interval graphs, co- comparability graphs, diamond graphs). In this paper we introduce an extension of diamond graphs, namely the k-diamond graphs, and give a dynamic program- ming algorithm to solve WFVP in linear time on this class of graphs. Other than solving an open question, this algorithm allows an efficient exploration of a neigh- borhood structure that can be defined by using such a class of graphs. We used this neighborhood structure inside our Iterated Tabu Search heuristic. Our exten- sive experimental results show the effectiveness of this heuristic in improving the solution provided by a 2-approximate algorithm for the WFVP on general graphs.

A Tabu Search Heuristic Based on k-Diamonds for the Weighted Feedback Vertex Set Problem

CARRABS, FRANCESCO;CERULLI, Raffaele;GENTILI, Monica;
2011-01-01

Abstract

Given an undirected and vertex weighted graph G = (V,E,w), the Weighted Feedback Vertex Problem (WFVP) consists of finding a subset F V of vertices of minimum weight such that each cycle in G contains at least one vertex in F. The WFVP on general graphs is known to be NP-hard and to be polynomially solvable on some special classes of graphs (e.g., interval graphs, co- comparability graphs, diamond graphs). In this paper we introduce an extension of diamond graphs, namely the k-diamond graphs, and give a dynamic program- ming algorithm to solve WFVP in linear time on this class of graphs. Other than solving an open question, this algorithm allows an efficient exploration of a neigh- borhood structure that can be defined by using such a class of graphs. We used this neighborhood structure inside our Iterated Tabu Search heuristic. Our exten- sive experimental results show the effectiveness of this heuristic in improving the solution provided by a 2-approximate algorithm for the WFVP on general graphs.
2011
9783642215261
9783642215278
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4570857
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 8
social impact