9

A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper. Bojan Mohar: "Face Covers and the Genus Problem for Apex Graphs" Journal of Combinatorial Theory, Series B 82, 102-117 (2001)


6

Question (1) is easy polynomial time. As Juho has already mentioned in comments, the graphs that can be partitioned into a clique and an independent set are the split graphs. They can be recognized and partitioned in polynomial time, and all valid partitions (if there are more than one) differ by only a single vertex and can also be found in polynomial time (...


5

The NP-hardness proof for CLIQUE in the book by Garey and Johnson shows that the following problem is NP-complete: Instance: An integer $k$; a $k$-partite graph $G=(V,E)$ Question: Does $G$ contain a $k$-clique? Here is a construction that shows NP-completeness of your problem variant: Let $G$ and $k$ be as in the proof in Garey and Johnson Let $H_1$ ...


3

From the standard machinery, we can quickly deduce that there is a quasilinear-time reduction from $\textrm{IS-H}$ to $\textrm{IS}$. (But see below if quasilinear isn't good enough for you.) Recall that $\textrm{3-SAT}$ is hard for $\mathsf{NTIME}[t(n)]$ under reductions that run in time $\tilde{O}(t(n))$, and in particular the resulting 3-CNF formula has ...


2

The LP in question is a maximization over a bounded polytope, hence the optimal value is attained at a vertex of the polytope. Moreover, any vertex can be described as a unique solution of a system of linear equations obtained by replacing inequalities with equalities in a subset of the inequalities defining the problem. Here, the polytope is defined by $$\...


1

I don't think the Bollobás paper asserts the bound on the independence number; rather, it seems to me that it asserts that for any given maximum degree $\Delta$ and lower bound on the girth $g$, there exists graphs of degree at most $\Delta$ and girth at least $g$ with independence ratio at most $2\log \Delta/\Delta$. In contrast, as you mention, the Frieze ...


1

This is discussed in a related cstheory post: LP relaxation of independent set That post cites this publication: [1] Nemhauser, G.L., Trotter, L.E. Vertex packings: Structural properties and algorithms. Mathematical Programming 8, 232–248 (1975). https://doi.org/10.1007/BF01580444 That publication in turn cites a few others, including these: [2] ...


1

Actually, there is a simple gadget to remove vertices of degree larger than three. See, e.g., the answer here. Note that this gadget keeps planarity.


1

I am not as convinced as @Andrew Morgan is that this is "fair standard fare", and would also welcome pointers to a citable reduction. In particular, I do not see how to maintain a linear blowup if $k$ depends on $n$, because encoding that the independent set is large enough with linear blowup seems to require a simulation of any threshold gate by a linear-...


Only top voted, non community-wiki answers of a minimum length are eligible