Graph-Theoretic Concepts in Computer Science

The structural and algorithmic properties of interval graphs have received considerable attention. While many aspects of this important and classical class of graphs are well understood, some old problems are still open. One such problem is the so-called interval count problem, which asks for the minimum number of different interval lengths needed to represent a given interval graph. Whereas graphs of interval count 1 coincide with unit interval graphs, not much is known about graphs of interval count 2. In this talks we will survey some recent results and discuss several open problems related to interval count 2 graphs.

The setting considered in this talk is that of a structure S constructed over a given network G and intended to efficiently support some service on it (e.g., a distributed database or a query-answering oracle.) Such a structure is required to ensure certain desirable properties with respect to G. However, a failure event F might damage some of the network’s vertices and edges, and cause S to malfunction. We are interested in ways of making S fault-tolerant, namely, reinforcing it so that following a failure event, its surviving part continues to satisfy the requirements. The talk will distinguish between two types of fault-tolerance, termed rigid and competitive fault tolerance, compare these two notions, and illustrate them on a number of examples.

We consider a graph with colored edges and study the following two problems.

(i) Suppose first that the number of colors is two, say red and blue. A nonnegative real vector on the edges is said to be

balanced

if the red sum equals the blue sum at every vertex. A

balanced subgraph

is a subgraph whose characteristic vector is balanced (i.e., red degree equals blue degree at every vertex). By a

sum

(respectively,

fractional sum

) of cycles we mean a nonnegative integral (respectively, nonnegative rational) combination of characteristic vectors of cycles. Similarly, we define sum and fractional sum of balanced subgraphs. We show that a balanced sum of cycles is a fractional sum of balanced subgraphs.

(ii) Next we consider the problem of finding a necessary and sufficient condition for the existence of a balanced subgraph containing a given edge. This problem is easily reduced to the alternating reachability problem, defined as follows. Given an edge colored graph (here we allow ≥ 2 colors) a trail (vertices may repeat but not edges) is called

alternating

when successive edges have different colors. Given a set of vertices called

terminals

, the

alternating reachability

problem is to find an alternating trail connecting distinct terminals, if one exists. By reduction to the classical case of searching for an augmenting path with respect to a matching we show that either there exists an alternating trail connecting distinct terminals or there exists an obstacle, called a

Tutte set

, to the existence of such trails. We also give a Gallai-Edmonds decomposition of the set of nonterminals.

This work started when Uri Peled and Murali Srinivasan met in Caesarea Edmond Benjamin de Rothschild Foundation Institute for Interdisciplinary Applications of Computer Science at the University of Haifa, Israel during May–June 2003. This led to many interesting questions and some of them are still open. In this talk we would like to discuss some of them.

During WG 2012 there was a Student Poster Session, where the following posters were presented (alphabetically ordered by student’s last name).

Finding minimal triangulations of graphs is a well-studied problem with many applications, for instance as first step for efficiently computing graph decompositions in terms of clique separators. Computing a minimal triangulation can be done in

O

(

nm

) time and much effort has been invested to improve this time bound for general and special graphs. We propose a recursive algorithm which works for general graphs and runs in linear time if the input is a claw-free graph and the length of its longest path is bounded by a fixed value

k

. More precisely, our algorithm runs in

O

(

f

 + 

km

) time if the input is a claw-free graph, where

f

is the number of fill edges added, and

k

is the height of the execution tree; we find all the clique minimal separators of the input graph at the same time. Our algorithm can be modified to a robust algorithm which runs within the same time bound: given a non-claw free input, it either triangulates the graph or reports a claw.

The only available combinatorial algorithm for the minimum weighted clique cover (

mwcc

) in claw-free perfect graphs is due to Hsu and Nemhauser [10] and dates back to 1984. More recently, Chudnovsky and Seymour [3] introduced a composition operation, strip-composition, in order to define their structural results for claw-free graphs; however, this composition operation is general and applies to non-claw-free graphs as well. In this paper, we show that a

mwcc

of a perfect strip-composed graph, with the basic graphs belonging to a class

${\cal G}$

, can be found in polynomial time, provided that the

mwcc

problem can be solved on

${\cal G}$

in polynomial time. We also design a new, more efficient, combinatorial algorithm for the

mwcc

problem on strip-composed claw-free perfect graphs.

We study the complexity of the Graph Isomorphism problem on graph classes that are characterized by a finite number of forbidden induced subgraphs, focusing mostly on the case of two forbidden subgraphs. We show hardness results and develop techniques for the structural analysis of such graph classes, which applied to the case of two forbidden subgraphs give the following results: A dichotomy into isomorphism complete and polynomial-time solvable graph classes for all but finitely many cases, whenever neither of the forbidden graphs is a clique, a pan, or a complement of these graphs. Further reducing the remaining open cases we show that (with respect to graph isomorphism) forbidding a pan is equivalent to forbidding a clique of size three.

The class of

D-dotted interval

(

D

-DI) graphs is the class of intersection graphs of arithmetic progressions with jump (common difference) at most

D

. We consider various classical graph-theoretic optimization problems in

D

-DI graphs of arbitrarily, but fixed,

D

.

We show that

Maximum Independent Set

,

Minimum Vertex Cover

, and

Minimum Dominating Set

can be solved in polynomial time in this graph class, answering an open question posed by Jiang

(Inf. Processing Letters, 98(1):29–33, 2006)

. We also show that

Minimum Vertex Cover

can be approximated within a factor of (1 + 

ε

) for any

ε

 > 0 in linear time. This algorithm generalizes to a wide class of deletion problems including the classical

Minimum Feedback Vertex Set

and

Minimum Planar Deletion

problems.

Our algorithms are based on classical results in algorithmic graph theory and new structural properties of

D

-DI graphs that may be of independent interest.

Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for

t

-interval graphs when

t

 ≥ 3 and polynomial-time solvable when

t

 = 1. The problem is also known to be NP-complete in

t

-track graphs when

t

 ≥ 4 and polynomial-time solvable when

t

 ≤ 2. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called

t

-circular interval graphs and

t

-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time

t

-approximation algorithm for WEIGHTED MAXIMUM CLIQUE on

t

-interval graphs, improving earlier work with approximation ratio 4

t

.

The stable roommates problem with payments has as input a graph

G

 = (

V

,

E

) with an edge weighting

w

:

E

 → ℝ

 + 

and the problem is to find a stable solution. A solution is a matching

M

with a vector

$p\in{\mathbb R}^V_+$

that satisfies

p

u

 + 

p

v

 = 

w

(

uv

) for all

uv

 ∈ 

M

and

p

u

 = 0 for all

u

unmatched in

M

. A solution is stable if it prevents blocking pairs, i.e., pairs of adjacent vertices

u

and

v

with

p

u

 + 

p

v

 < 

w

(

uv

). By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a simple constructive proof for showing that every yes-instance of the stable roommates problem with payments allows a path of linear length that starts in an arbitrary unstable solution and that ends in a stable solution. This result generalizes a result of Chen, Fujishige and Yang for bipartite instances to general instances. We also show that the problems

Blocking Pairs

and

Blocking Value

, which are to find a solution with a minimum number of blocking pairs or a minimum total blocking value, respectively, are

NP

-hard. Finally, we prove that the variant of the first problem, in which the number of blocking pairs must be minimized with respect to some fixed matching, is

NP

-hard, whereas this variant of the second problem is polynomial-time solvable.

Connectivity properties are very important characteristics of a graph. Whereas it is usually referred to as a measure of a graph’s vulnerability, a relatively new approach discusses a graph’s

average connectivity

as a measure for the graph’s performance in some areas, such as communication. This paper deals with Tower of Hanoi variants played on digraphs, and proves they can be grouped into two categories, based on a certain connectivity attribute to be defined in the sequel.

A major source for Tower of Hanoi variants is achieved by adding pegs and/or restricting direct moves between certain pairs of pegs. It is natural to represent a variant of this kind by a directed graph whose vertices are the pegs, and an arc from one vertex to another indicates that it is allowed to move a disk from the former peg to the latter, provided that the usual rules are not violated. We denote the number of pegs by

h

. For example, the variant with no restrictions on moves is represented by the Complete

K

h

graph; the variant in which the pegs constitute a cycle and moves are allowed only in one direction — by the uni-directional graph

Cyclic

h

.

For all 3-peg variants, the number of moves grows exponentially fast with

n

. However, for

h

 ≥ 4 peg variants, this is not the case. Whereas for

Cyclic

h

the number of moves is exponential for any

h

, for most of the other graphs it is sub-exponential. For example, for a path on 4 vertices it is

$O(\sqrt{n}3^{\sqrt{2n}})$

, for

n

disks.

This paper presents a necessary and sufficient condition for a graph to be an H-subexp, i.e., a graph for which the transfer of

n

disks from a peg to another requires sub-exponentially many moves as a function of

n

.

To this end we introduce the notion of a shed, as a graph property. A vertex

v

in a strongly-connected directed graph

G

 = (

V

,

E

) is a

shed

if the subgraph of

G

induced by

V

 − {

v

} contains a strongly connected subgraph on 3 or more vertices. Graphs with sheds will be shown to be much more efficient than those without sheds, for the particular domain of the Tower of Hanoi puzzle. Specifically we show how, given a graph with a shed, we can indeed move a tower of

n

disks from any peg to any other within

O

(2

εn

) moves, where

ε

 > 0 is arbitrarily small.

We study the problem of computing

h

-quasi planar drawings in linear area; in an

h

-quasi planar drawing the number of mutually crossing edges is at most

h

 − 1. We prove that every

n

-vertex partial

k

-tree admits a straight-line

h

-quasi planar drawing in

O

(

n

) area, where

h

depends on

k

but not on

n

. For specific sub-families of partial

k

-trees, we present ad-hoc algorithms that compute

h

-quasi planar drawings in linear area, such that

h

is significantly reduced with respect to the general result. Finally, we compare the notion of

h

-quasi planarity with the notion of

h

-planarity, where each edge is allowed to be crossed at most

h

times.

We consider directed planar graphs with an upward planar drawing on the rolling and standing cylinders. These classes extend the upward planar graphs in the plane. Here, we address the dual graphs. Our main result is a combinatorial characterization of these sets of upward planar graphs. It basically shows that the roles of the standing and the rolling cylinders are interchanged for their duals.

For an undirected graph

G

 = (

V

,

E

), we say that for ℓ,

u

,

v

 ∈ 

V

, ℓ separates

u

from

v

if the distance between

u

and ℓ differs from the distance from

v

to ℓ. A set of vertices

L

 ⊆ 

V

is a feasible solution if for every pair of vertices

u

,

v

 ∈ 

V

there is ℓ ∈ 

L

that separates

u

from

v

. The metric dimension of a graph is the minimum cardinality of such a feasible solution. Here, we extend this well-studied problem to the case where each vertex

v

has a non-negative cost, and the goal is to find a feasible solution with a minimum total cost. This weighted version is NP-hard since the unweighted variant is known to be NP-hard. We show polynomial time algorithms for the cases where

G

is a path, a tree, a cycle, a cograph, a

k

-edge-augmented tree (that is, a tree with additional

k

edges) for a constant value of

k

, and a (not necessarily complete) wheel. The results for paths, trees, cycles, and complete wheels extend known polynomial time algorithms for the unweighted version, whereas the other results are the first known polynomial time algorithms for these classes of graphs even for the unweighted version. Next, we extend the set of graph classes for which computing the unweighted metric dimension of a graph is known to be NPC by showing that for split graphs, bipartite graphs, co-bipartite graphs, and line graphs of bipartite graphs, the problem of computing the unweighted metric dimension of the graph is NPC.

An

L

(2,1)-labeling of a graph is a mapping from its vertex set into a set of integers {0,..,

k

} such that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. The main result of the paper is an algorithm finding an optimal

L

(2,1)-labeling of a graph (i.e. an

L

(2,1)-labeling in which the largest label is the least possible) in time

O

*

(7.4922

n

) and polynomial space. Moreover, a new interesting extremal graph theoretic problem is defined and solved.

The local minimum degree of a graph is the minimum degree reached by means of a series of local complementations. In this paper, we investigate on this quantity which plays an important role in quantum computation and quantum error correcting codes.

First, we show that the local minimum degree of the Paley graph of order

p

is greater than

$\sqrt{p} - \frac{3}{2}$

, which is, up to our knowledge, the highest known bound on an explicit family of graphs. Probabilistic methods allows us to derive the existence of an infinite number of graphs whose local minimum degree is linear in their order with constant 0.189 for graphs in general and 0.110 for bipartite graphs. As regards the computational complexity of the decision problem associated with the local minimum degree, we show that it is NP-complete and that there exists no

l

-approximation algorithm for this problem for any constant

l

unless

P

 = 

NP

.

We define the stable degree

s

(

G

) of a graph

G

by

s

(

G

) =  min

U

max

v

 ∈ 

U

d

G

(

v

), where the minimum is taken over all maximal independent sets

U

of

G

. For this new parameter we prove the following. Deciding whether a graph has stable degree at most

k

is NP-complete for every fixed

k

 ≥ 3; and the stable degree is hard to approximate. For asteroidal triple-free graphs and graphs of bounded asteroidal number the stable degree can be computed in polynomial time. For graphs in these classes the treewidth is bounded from below and above in terms of the stable degree.

We study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. Our main result is a kernel of size at most 9

k

vertices for the

Planar Maximum Nonseparating Independent Set

problem. A direct consequence of this result is that

Planar Connected Vertex Cover

has no kernel with at most 9/8

k

vertices, assuming

P

 ≠ 

NP

. We also show a very simple 5

k

-vertices kernel for

Planar Max Leaf

, which results in a lower bound of 5/4

k

vertices for the kernel of

Planar Connected Dominating Set

(also under

P

 ≠ 

NP

).

We consider a decision version of the problem of finding the minimum number of vertices whose deletion results in a graph without even cycles. While this problem is a natural analogue of the

Odd Cycle Transversal

problem (which asks for a subset of vertices to delete to make the resulting graph bipartite), surprisingly this problem is not well studied. We first observe that this problem is NP-complete and give a constant factor approximation algorithm. Then we address the problem in parameterized complexity framework with the solution size

k

as a parameter. We give an algorithm running in time

O

*

(2

O

(

k

)

) for the problem and give an

O

(

k

2

) vertex kernel. (We write

O

*

(

f

(

k

)) for a time complexity of the form

O

(

f

(

k

)

n

O

(1)

), where

f

(

k

) grows exponentially with

k

.)

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most one, and the size of the bisection is the number of edges which go across the two parts.

Every graph with

m

edges has a bisection of size at least ⌈

m

/2 ⌉, and this bound is sharp for infinitely many graphs. Therefore, Gutin and Yeo considered the parameterized complexity of deciding whether an input graph with

m

edges has a bisection of size at least ⌈

m

/2 ⌉ + 

k

, where

k

is the parameter. They showed fixed-parameter tractability of this problem, and gave a kernel with

O

(

k

2

) vertices.

Here, we improve the kernel size to

O

(

k

) vertices. Under the Exponential Time Hypothesis, this result is best possible up to constant factors.

We study parameterized complexity of a generalization of the classical

Feedback Vertex Set

problem, namely the

Group Feedback Vertex Set

problem: we are given a graph

G

with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of

G

that evaluate to a non-null element of the group. This problem generalizes not only

Feedback Vertex Set

, but also

Subset Feedback Vertex Set

,

Multiway Cut

and

Odd Cycle Transversal

. Completing the results of Guillemot [Discr. Opt. 2011], we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a blackbox performing group operations.

Graph spanners are sparse subgraphs that preserve the distances of the original graph, up to some small multiplicative factor or additive term (known as the

stretch

of the spanner). A number of algorithms are known for constructing sparse spanners with small multiplicative or additive stretch. Recently, the problem of constructing

fault-tolerant multiplicative

spanners for general graphs was given some algorithms. This paper addresses the analogous problem of constructing

fault tolerant additive

spanners for general graphs.

We establish the following general result. Given an

n

-vertex graph

G

, if

H

1

is an ordinary additive spanner for

G

with additive stretch

α

, and

H

2

is a fault tolerant multiplicative spanner for

G

, resilient against up to

f

edge failures, with multiplicative stretch

μ

, then

H

 = 

H

1

 ∪ 

H

2

is an additive fault tolerant spanner of

G

, resilient against up to

f

edge failures, with additive stretch

$O(\tilde{f}(\alpha+\mu))$

where

$\tilde{f}$

is the number of failures that have actually occurred

$(\tilde{f}\leq f)$

.

This allows us to derive a poly-time algorithm

${\texttt Span}^{f-t}_{add}$

for constructing an additive fault tolerant spanner

H

of

G

, relying on the existence of algorithms for constructing fault tolerant multiplicative spanners and (ordinary) additive spanners. In particular, based on some known spanner construction algorithms, we show how to construct for any

n

-vertex graph

G

an additive fault tolerant spanner with additive stretch

$O(\tilde{f})$

and size

O

(

fn

4/3

).

We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant

l

, outputs a directed Steiner tree of cost no larger than 2(

l

 − 1)(ln

n

 + 1) times the cost of the minimum

l

-restricted Steiner tree. We derive from this result that 1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of

O

(log

n

), and 2) the tree cover problem on directed graphs can also be approximated within a factor of

O

(log

n

).

It is a folklore result that testing whether a given system of equations with two variables per inequality (a 2VPI system) of the form x _i  − x _j  = c _ij is solvable, can be done efficiently not only by Gaussian elimination but also by shortest-path computation on an associated constraint graph. However, when the system is infeasible and one wishes to delete a minimum weight set of inequalities to obtain feasibility (MinFs2=), this task becomes NP-complete.Our main result is a 2-approximation for the problem MinFs2= for the case when the constraint graph is planar using a primal-dual approach. We also give an α-approximation for the related maximization problem MaxFs2= where the goal is to maximize the weight of feasible inequalities. Here, α denotes the arboricity of the constraint graph. Our results extend to obtain constant factor approximations for the case when the domains of the variables are further restricted.

We consider a graph parameter, the

hydra number

, arising from an optimization problem for Horn formulas in propositional logic. The hydra number of a graph

G

 = (

V

,

E

) is the minimal number of hyperarcs of the form

u

,

v

 → 

w

required in a directed hypergraph

H

 = (

V

,

F

), such that for every pair (

u

,

v

), the set of vertices reachable in

H

from {

u

,

v

} is the entire vertex set

V

if (

u

,

v

) ∈ 

E

, and it is {

u

,

v

} otherwise. Here reachability is defined by the standard forward chaining or marking algorithm.

Various bounds are given for the hydra number. We show that the hydra number of a graph can be upper bounded by the number of edges plus the path cover number of its line graph, and this is a sharp bound for some graphs. On the other hand, we construct graphs with hydra number equal to the number of edges, but having arbitrarily large path cover number. Furthermore we characterize trees with low hydra number, give bounds for the hydra number of complete binary trees, discuss a related optimization problem and formulate several open problems.

We consider the following multi–level opinion spreading model on networks. Initially, each node gets a weight from the set {0,…,

k

 − 1}, where such a weight stands for the individuals conviction of a new idea or product. Then, by proceeding to rounds, each node updates its weight according to the weights of its neighbors. We are interested in the initial assignments of weights leading each node to get the value

k

 − 1 –e.g. unanimous maximum level acceptance– within a given number of rounds. We determine lower bounds on the sum of the initial weights of the nodes under the irreversible simple majority rules, where a node increases its weight if and only if the majority of its neighbors have a weight that is higher than its own one. Moreover, we provide constructive tight upper bounds for some class of regular topologies: rings, tori, and cliques.

We study the graphs

G

for which the hull number

h

(

G

) and the geodetic number

g

(

G

) with respect to

P

3

-convexity coincide. These two parameters correspond to the minimum cardinality of a set

U

of vertices of

G

such that the simple expansion process that iteratively adds to

U

, all vertices outside of

U

that have two neighbors in

U

, produces the whole vertex set of

G

either eventually or after one iteration, respectively. We establish numerous structural properties of the graphs

G

with

h

(

G

) = 

g

(

G

), which allow the constructive characterization as well as the efficient recognition of all triangle-free such graphs. Furthermore, we characterize the graphs

G

that satisfy

h

(

H

) = 

g

(

H

) for every induced subgraph

H

of

G

in terms of forbidden induced subgraphs.

In this paper we study properties of intersection graphs of

k

-bend paths in the rectangular grid. A

k

-bend path is a path with at most

k

90 degree turns. The class of graphs representable by intersections of

k

-bend paths is denoted by

B

k

-VPG. We show here that for every fixed

k

,

B

k

-VPG

$\subsetneq$

B

k

 + 1

-VPG and that recognition of graphs from

B

k

-VPG is NP-complete even when the input graph is given by a

B

k

 + 1

-VPG representation. We also show that the class

B

k

-VPG (for

k

 ≥ 1) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.

A graph

G

 = (

V

,

E

) is called

equistable

if there exist a positive integer

t

and a weight function

$w:V \longrightarrow \mathbb{N}$

such that

S

 ⊆ 

V

is a maximal stable set of

G

if and only if

w

(

S

) = 

t

. The function

w

, if exists, is called an

equistable function

of

G

. No combinatorial characterization of equistable graphs is known, and the complexity status of recognizing equistable graphs is open. It is not even known whether recognizing equistable graphs is in

NP

.

Let

k

be a positive integer. An equistable graph

G

 = (

V

,

E

) is said to be

k-equistable

if it admits an equistable function which is bounded by

k

. For every constant

k

, we present a polynomial time algorithm which decides whether an input graph is

k

-equistable.

A graph is a

multiclique

if its connected components are cliques. A graph is a

complete multipartite graph

if it is the complement of a multiclique. A graph is a

multiclique-multipartite graph

if its vertex set has a partition

U

,

W

such that

G(U)

is complete multipartite,

G(W)

is a multiclique and every two vertices

u(U

,

v(W

are adjacent. We describe a polynomial time algorithm to find in polygon-circle graphs a maximum induced complete multipartite subgraph containing an induced

K

2,2

. In addition, we describe polynomial time algorithms to find maximum induced multicliques and multiclique-multipartite subgraphs in circle graphs. These problems have applications for clustering of proteins by PPI criteria.

A

circle graph

is the intersection graph of a set of chords in a circle. Keil [

Discrete Applied Mathematics

, 42(1):51-63, 1993] proved that

Dominating Set

,

Connected Dominating Set

, and

Total Dominating Set

are

NP

-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction:

Dominating Set

,

Independent Dominating Set

,

Connected Dominating Set

,

Total Dominating Set

, and

Acyclic Dominating Set

are

W

[1]-hard in circle graphs, parameterized by the size of the solution.

Whereas both

Connected Dominating Set

and

Acyclic Dominating Set

are

W

[1]-hard in circle graphs, it turns out that

Connected Acyclic Dominating Set

is polynomial-time solvable in circle graphs.

If

T

is a

given

tree, deciding whether a circle graph has a dominating set isomorphic to

T

is

NP

-complete when

T

is in the input, and

FPT

when parameterized by |

V

(

T

)|. We prove that the FPT algorithm is subexponential.

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the

Elimination

problem as follows: given two graphs

G

and

H

, decide whether

H

can be obtained from

G

by |

V

(

G

)| − |

V

(

H

)| vertex eliminations. We study the parameterized complexity of the

Elimination

problem. We show that

Elimination

is

W

[1]-hard when parameterized by |

V

(

H

)|, even if both input graphs are split graphs, and

W

[2]-hard when parameterized by |

V

(

G

)| − |

V

(

H

)|, even if

H

is a complete graph. On the positive side, we show that

Elimination

admits a kernel with at most 5|

V

(

H

)| vertices in the case when

G

is connected and

H

is a complete graph, which is in sharp contrast to the

W

[1]-hardness of the related

Clique

problem. We also study the case when either

G

or

H

is tree. The computational complexity of the problem depends on which graph is assumed to be a tree: we show that

Elimination

can be solved in polynomial time when

H

is a tree, whereas it remains

NP

-complete when

G

is a tree.

We study the problem of finding small

s

–

t

separators that induce graphs having certain properties. It is known that finding a minimum clique

s

–

t

separator is polynomial-time solvable (Tarjan 1985), while for example the problems of finding a minimum

s

–

t

separator that is a connected graph or an independent set are fixed-parameter tractable (Marx, O’Sullivan and Razgon, manuscript). We extend these results the following way:

Finding a minimum

c

-connected

s

–

t

separator is FPT for

c

 = 2 and

W

[1]-hard for any

c

 ≥ 3.

Finding a minimum

s

–

t

separator with diameter at most

d

is

W

[1]-hard for any

d

 ≥ 2.

Finding a minimum

r

-regular

s

–

t

separator is

W

[1]-hard for any

r

 ≥ 1.

For any decidable graph property, finding a minimum

s

–

t

separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree.

We also show that finding a connected

s

–

t

separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless NP ⊆ coNP/poly.