Init

SetDirectory[NotebookDirectory[]];
Needs["Bulatov`common`"];
Needs["Bulatov`showGraphs`"];

$Post=($ContextPath=DeleteCases[$ContextPath,"Combinatorica`"|"GraphUtilities`"];#)&;

Utils

graphCoords[g_Graph]:=(
Thread[VertexList[g]->VertexCoordinates/.AbsoluteOptions[g]]
);

changeGraphStyle[g_Graph,style_]:=Module[{vcoords,gstyle,labelMap,adjMat,newOrder,newCoords,verts},
	vcoords=VertexCoordinates/.AbsoluteOptions[g,VertexCoordinates];
	Graph[VertexList@g,EdgeList@g,VertexCoordinates->vcoords,GraphStyle->style]
];

fadedGraph[g_Graph,vals_]:=Module[{vf},
Assert[Length@vals==Length@VertexList@g];
verts=VertexList@g;
edges=EdgeList@g;
vcoords=graphCoords@g;
vf[{xc_,yc_},name_,{w_,h_}]:=(
d1=Disk[{xc,yc},Max[w,h],{0,2Pi}];
{ColorData["Crayola"]["NavyBlue"],Opacity[vals[[name]]],d1}
);
Graph[verts,UndirectedEdge@@@edges,VertexShapeFunction->vf,VertexSize->{"Scaled",.1},VertexCoordinates->vcoords,ImageSize->Small]
];

pieGraph[g_Graph,vals_]:=Module[{vf},
Assert[Length@vals==Length@VertexList@g];
verts=VertexList@g;
edges=EdgeList@g;
vcoords=graphCoords@g;
vf[{xc_,yc_},name_,{w_,h_}]:=(
d0=Disk[{xc,yc},Max[w,h],{0,2Pi}];
d1=Disk[{xc,yc},Max[w,h],{Pi/2,Pi/2-2Pi vals[[name]]}];
(*d2=Disk[{xc,yc},Max[w,h],{0,2Pi}];*)
{Opacity[0.],d0,Opacity[1.],ColorData["Crayola"]["NavyBlue"],d1}
);
Graph[verts,UndirectedEdge@@@edges,VertexShapeFunction->vf,VertexSize->{"Scaled",.1},VertexCoordinates->vcoords,ImageSize->Small]
];

highlightGraph[g_Graph,selected_]:=Module[{vf},
verts=VertexList@g;
edges=EdgeList@g;
vcoords=graphCoords@g;
vf[{xc_,yc_},name_,{w_,h_}]:=(
d1=Disk[{xc,yc},Max[w,h],{0,2Pi}];
{ColorData["Crayola"]["NavyBlue"],If[MemberQ[selected,name],Opacity[1.],Opacity[0.]],d1}
);
Graph[verts,UndirectedEdge@@@edges,VertexShapeFunction->vf,VertexSize->{"Scaled",.1},VertexCoordinates->vcoords,ImageSize->Small]
];

(* takes graph complement but saves coordinates *)
graphComplement[g_]:=(
verts=VertexList@g;
edges=EdgeList@GraphComplement@g;
vcoords=graphCoords@g;
Graph[verts,edges,VertexCoordinates->vcoords]
);

(* return all maximal cliques in a graph *)
getMaximalCliques[g_Graph]:=(
getNb[verts_]:=VertexList[NeighborhoodGraph[g,verts]]∖verts;
extend[clique_]:=(
candidates=clique⋃{#}&/@getNb[clique];
cliques=Select[candidates,CompleteGraphQ@Subgraph[g,#]&];
If[cliques≠{},cliques,{clique}]
);
extendSet[cliqueSet_]:=Union@fl1[extend/@cliqueSet];

FixedPoint[extendSet,List@@@EdgeList@g]
);

getMaximalIndsets[g_]:=maximalCliques@GraphComplement@g;

(* returns all independent sets in a graph *)
getIndsets[gg_Graph]:=(
edge2clause[e_]:=!(e[[1]]&&e[[2]]);
clauses=edge2clause/@EdgeList[gg];
formula=And@@clauses;
vars=VertexList[gg];
instances=SatisfiabilityInstances[formula,vars,All];
Extract[vars,Position[#,True]]&/@instances
);

getCliques[g_]:=getIndsets@GraphComplement@g;

(* gives solution of independent set LP with edge constraints *)
solveEdgeLP[g_Graph]:=(
Clear[x];
edgeCons[a_\[UndirectedEdge]b_]:=(x[a]+x[b]≤1);
vertCons[a_]:=(0≤x[a]);
conses=Flatten[{edgeCons/@EdgeList@g,vertCons/@VertexList@g}];
cons=And@@conses;
vars=x/@VertexList[g];
vec=ConstantArray[1,\[LeftBracketingBar]vars\[RightBracketingBar]];
sol=Maximize[{vars.vec,cons},vars];
vars/.sol[[2]]
);

(* visualizes solution of edgeLP *)
visEdgeLP[g_Graph]:=(
xsol=solveEdgeLP[g];
pieGraph[g,xsol]
);

solveCliqueLP[g_Graph]:=(
Clear[x];
cliqueCons[clique_]:=(Total[x/@clique]≤1);
vertCons[a_]:=(0≤x[a]≤1);
conses=Flatten[{cliqueCons/@getMaximalCliques@g,vertCons/@VertexList@g}];
cons=And@@conses;
vars=x/@VertexList[g];
vec=ConstantArray[1,\[LeftBracketingBar]vars\[RightBracketingBar]];
sol=Maximize[{vars.vec,cons},vars];
vars/.sol[[2]]
);

visCliqueLP[g_Graph]:=(
xsol=solveCliqueLP[g];
pieGraph[g,xsol]
);

(* checks if edge LP is completely ambiguous for this graph *)
badEdgeLP[g_Graph]:=(
goodOnes=Select[solveEdgeLP[g],N[#]≠.5&];
Length@goodOnes==0
);

Extra

Needs["Bulatov`showGraphs`"];
graphs=getGraphs[{1,6},"Connected","Planar","Perfect","Bridgeless"];
numMaxSets[gname_]:=CoefficientList[GraphData[gname,"IndependencePolynomial"][x],x]//Last;
goodGraphs=Select[graphs,numMaxSets[#]==1&];

Tooltip[Show[visEdgeLP[GraphData[#]],ImageSize->Tiny],#]&/@(getGraphs[7,"Planar","Connected",!"Bipartite"][[;;50]])

graphs=getGraphs[5,"Planar","Connected",!"Bipartite"];
pics=Show[visEdgeLP[GraphData[#]],ImageSize->Tiny]&/@graphs

Get graphs with bad edge LP

(* checks if edge LP is completely ambiguous for this graph *)
badEdgeLP[g_Graph]:=(
goodOnes=Select[solveEdgeLP[g],N[#]≠.5&];
Length@goodOnes==0
);

graphs=getGraphs[7,"Planar","Connected",!"Bipartite"][[;;25]];
graphs2=Select[graphs,badEdgeLP@GraphData@#&]

graphs=getGraphs[7,"Planar","Connected","Bridgeless",!"Bipartite"][[;;50]];
badGraphs=Select[graphs,badEdgeLP[GraphData[#]]&];

Post

g=GraphData[{6,87}];
gc=graphComplement@g;

pic1=Show[highlightGraph[g,{1,2,3}],PlotLabel->"largest independent set"];
pic2=Show[highlightGraph[g,{1,2,3,6}],PlotLabel->"not independent set"];
pic3=Show[highlightGraph[g,{2,3}],PlotLabel->"not largest"];
pic4=GraphicsRow[{pic1,pic2,pic3}]
Export["blog-lp/indsets.png",pic4];

pic1=Show[highlightGraph[gc,{1,2,3}],PlotLabel->"largest clique"];
pic2=Show[highlightGraph[gc,{1,2,3,6}],PlotLabel->"not clique"];
pic3=Show[highlightGraph[gc,{2,3}],PlotLabel->"not largest"];
pic4=GraphicsRow[{pic1,pic2,pic3}]
Export["blog-lp/cliques.png",pic4];

g=CycleGraph@4//changeGraphStyle[#,"DiagramBlack"]&
Export["blog-lp/cycle.png",Show@g];

g=GraphData[{7,119}]//changeGraphStyle[#,"DiagramBlack"]&;
g=relabelGraph[g,Ordering@{6,1,5,7,3,2,4}];
pic1=Show[visEdgeLP@g,ImageSize->250]

pic2=Show[highlightGraph[g,{1,5,6,7}],ImageSize->250];

pic3=GraphicsRow[{pic1,pic2}]

Export["blog-lp/half-integral2.png",pic3]

graphs=getGraphs[7,"Planar","Connected",!"Bipartite"][[;;25]];
pics=Show[visEdgeLP[GraphData[#]]]&/@graphs;
pic=GraphicsGrid[Partition[pics,Sqrt@Length@pics],ImageSize->600]

Export["blog-lp/edge-lps.png",pic];

g=GraphData["ButterflyGraph"];
pic=Show[visEdgeLP@g,ImageSize->300]
Export["blog-lp/butterfly.png",pic]

pic=Show[visCliqueLP@g,ImageSize->300]

Export["blog-lp/butterfly2.png",pic];

pic=Show[visCliqueLP[GraphData@{"Cubic",{10,11}}],ImageSize->300]

Export["blog-lp/cubic-third.png",pic]

graphs=getGraphs[8,"Planar","Connected","Bridgeless",!"Bipartite"];
badGraphs=Select[graphs,badEdgeLP[GraphData[#]]&];
pics=Show[visCliqueLP[GraphData[#]]]&/@badGraphs[[;;16]];

pic1=GraphicsGrid[Partition[pics,4],ImageSize->600]
Export["blog-lp/clique-lp.png",pic1]