Abstract In online edge- and node-deletion problems the input arrives node by node and an algorithm has to delete nodes or edges in order to keep the input graph in a given graph class $$\Pi $$ Π at all times. We consider only hereditary properties $$\Pi $$ Π , for which optimal online algorithms exist and which can be characterized by a set of forbidden subgraphs $${{\mathcal{F}}}$$ F and analyze the advice complexity of getting an optimal solution. We give almost tight bounds on the Delayed Connected $${{\mathcal{F}}}$$ F -Node-Deletion Problem, where all graphs of the family $${\mathcal{F}}$$ F have to be connected and almost tight lower and upper bounds for the Delayed $$H$$ H -Node-Deletion Problem, where there is one forbidden induced subgraph H that may be connected or not. For the Delayed $$H$$ H -Node-Deletion Problem the advice complexity is basically an easy function of the size of the biggest component in H. Additionally, we give tight bounds on the Delayed Connected $${\mathcal{F}}$$ F -Edge-Deletion Problem, where we have an arbitrary number of forbidden connected graphs. For the latter result we present an algorithm that computes the advice complexity directly from $${\mathcal{F}}$$ F . We give a separate analysis for the Delayed Connected $$H$$ H -Edge-Deletion Problem, which is less general but admits a bound that is easier to compute.

The protein folding problem (PFP) is an important issue in bioinformatics and biochemical physics. One of the most widely studied models of protein folding is the hydrophobic-polar (HP) model introduced by Dill. The PFP in the three-dimensional (3D) lattice HP model has been shown to be NP-complete; the proposed algorithms for solving the problem can therefore only find near-optimal energy structures for most long benchmark sequences within acceptable time periods. In this paper, we propose a novel algorithm based on the branch-and-bound approach to solve the PFP in the 3D lattice HP model. For 10 48-monomer benchmark sequences, our proposed algorithm finds the lowest energies so far within comparable computation times than previous methods.

Given a graph G=(V, E), an s-plex S\subseteq V is a vertex subset such that for v\in S the degree of v in G[S] is at least |S|-s. An s-plex bipartition \mathcal{P}=(V_1, V_2) is a bipartition of G=(V, E), V=V_1\uplus V_2, satisfying that both V_1 and V_2 are s-plexes. Given an instance G=(V, E) and a parameter k, the s-Plex Bipartition problem asks whether there exists an s-plex bipartition of G such that min{|V_1|, |V_2|\}\leq k. The s-Plex Bipartition problem is NP-complete. However, it is still open whether this problem is fixed-parameter tractable. In this paper, we give a fixed-parameter algorithm for 2-Plex Bipartition running in time O*(2.4143^k). A graph G = (V, E) is called defective (p, d)-colorable if it admits a vertex coloring with p colors such that each color class in G induces a subgraph of maximum degree at most d. A graph G admits an s-plex bipartition if and only if the complement graph of G, \bar{G}, admits a defective (2, s-1)-coloring such that one of the two color classes is of size at most k. By applying our fixed-parameter algorithm as a subroutine, one can find a defective (2,1)-coloring with one of the two colors of minimum cardinality for a given graph in O*(1.5539^n) time where n is the number of vertices in the input graph.