Vertex cover
=======================

Description
-----------

This example tries to solve the well-known NP-complete problem of Vertex Cover, by means of the so called simple Kernel P systems (skP systems).

Model
-----

The corresponding P-Lingua file is the following::

	@model<simple_kernel_psystems>

	def main()
	{
	  call vertex_cover();
	}

	def vertex_cover()
	{
	  call init_cells();  
	  call init_multisets();  
	  call init_rules();
	}

	def init_cells()
	{
	  @mu = [[]'1 []'2]'0;
	}

	def init_multisets()
	{
	  @ms(1) = S;
	  @ms(2) = A{1},s;
	  @ms(2) += A{e{i,1},e{i,2}} : 1<=i<=ne;

	  /* Environment alphabet: */
	}

	def init_rules()
	{

	  /* C1 */
	  /* r1,1 */ @guard {>=+T} ? [S]'1 --> [yes]'0;
	  /* r1,2 */ @guard {>=+F} && {>=-T} ? [S]'1 --> [no]'0;


	  /* C2 */
	  /* r2,i */ [A{i}]'2 |--> [B{i},A{i+1}]'2 [A{i+1}]'2 : 1<=i<n;
	  /* r2,n */ [A{n}]'2 |--> [B{n},X{1}]'2 [X{1}]'2;
	  /* r2,n+i */ @guard {=+X{1}} ? [B{i}]'2 --> [B{i},b]'2 : 1<=i<=n;
	  /* r2,2n+i */ [X{i}]'2 --> [X{i+1}]'2 : 1<=i<=2;
	  /* r2,2n+3 */ @guard {>+b*k}&&{=+X{2}} || 
					|{{=+A{i1,j1}}&&{=-B{i1}}&&{=-B{j1}}&&{=+X{2}}}:{1<=i1<n,2<=j1<=n} ? 
					[s]'2 --> []'2;
	  /* r2,2n+4 */ [X{3},s]'2 --> [T]'1;
	  /* r2,2n+5 */ @guard {=-s} ? [X{3}]'2 --> [F]'1;
	  
	}

Files
-----

.. container:: boldlink

    * `Custom applications <http://www.gcn.us.es/redmine/dmsf/files/2962/download>`_, defining the needed input and output tables for Vertex Cover problem.
    * `Model file <http://www.gcn.us.es/redmine/dmsf/files/2960/download>`_, P-Lingua file with the parametrized file specifying the family of P systems for solving the Vertex cover problem. The custom interface enable the user to introduce the data corresponding to each different scenario.
    * `Scenario file <http://www.gcn.us.es/redmine/dmsf/files/2961/download>`_, for a specific instance of the problem.

References
----------

* `Computational Efficiency of Cellular Division in Tissue-like Membrane Systems <http://www.imt.ro/romjist/Volum11/Number11_3/pdf/02-Diaz-Pernil.pdf>`_ (`detailed publication info <http://www.gcn.us.es/?q=node/357>`_).