In VCP4 problem, it is asked to find a set S⊆V of minimum size such that G[V\S] contains no path on 4 vertices, in a given graph G=(V,E). We prove that it is APX-complete for 3-regular graphs as well as 3-regular bipartite graphs. We show that a greedy based algorithm approximates VCP4 within a factor of 2 for regular graphs. We also show that VCP4 is APX-complete for K1, 4-free graphs and a local ratio based algorithm generates a solution which is within a factor of 3. © 2014 Elsevier B.V.

Sounaka Mishra

Department of Mathematics

Approximation algorithms

Graphic methods

APX-COMPLETE

Bipartite graphs

Graph G

K1 4-FREE GRAPH

LOCAL RATIO

Regular graphs

Vertex cover

Vertex Cover problems

Graph theory

Fulltext

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Discrete Applied Mathematics

In this paper, we develop approximation algorithms for a few node deletion problems when the input is restricted to be a bipartite graph. We look at node deletion problems for non-trivial properties which can be characterized by forbidden structure which has a bounded intersection with both the bipartitions. The approximation factors obtained directly depend upon the size of the largest such intersection. Special instances of this general problem include problems such as the Minimum Chain Vertex Deletion, Minimum Dissociation Vertex Deletion, Minimum Bipartite Claw Vertex Deletion, Minimum Bi-complement Vertex Deletion and Minimum Bipartite Threshold Vertex Deletion problems. The algorithms are based upon the techniques of linear programming and iterative rounding. We also use the node deletion algorithms to marginally improve the trivial approximation factor for complementary problem of determining the size of the maximum sized vertex induced subgraph lying in the given graph class and prove the APX-completeness of all of these problems. © 2014 Elsevier B.V.

Theoretical Computer Science

Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization

On the vertexk-path cover

Information Processing Letters

The vertex cover problem in cubic graphs

Journal of Computer and System Sciences

A generalization of Nemhauser and Trotterʼs local optimization theorem

Minimum <mml:math altimg="si1.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mi>k</mml:mi></mml:math>-path vertex cover

Computational complexity of minimum P4 vertex cover problem for regular and K 1, 4-free graphs

Journal	Data powered by TypesetDiscrete Applied Mathematics
Publisher	Data powered by TypesetElsevier B.V.
ISSN	0166218X
Open Access	Yes