Graph-Theoretic Concepts in Computer Science

We prove a general duality theorem for width parameters in combinatorial structures such as graphs and matroids. It implies the classical such theorems for path-width, tree-width, branch-width and rank-width, and gives rise to new width parameters with associated duality theorems. The dense substructures witnessing large width are presented in a unified way akin to tangles, as orientations of separation systems satisfying certain consistency axioms.

We tackle

local distributed testing

of graph properties. This framework is well suited to contexts in which data dispersed among the nodes of a network can be collected by some central authority (like in, e.g., sensor networks). In local distributed testing, each node can provide the central authority with just a few information about what it perceives from its neighboring environment, and, based on the collected information, the central authority is aiming at deciding whether or not the network satisfies some property. We analyze in depth the prominent example of checking

cycle-freeness

, and establish tight bounds on the amount of information to be transferred by each node to the central authority for deciding cycle-freeness. In particular, we show that distributedly testing cycle-freeness requires at least

$$\lceil \log d \rceil -1$$

bits of information per node in graphs with maximum degree

$$d$$

, even for connected graphs. Our proof is based on a novel version of the seminal result by Naor and Stockmeyer (1995) enabling to reduce the study of certain kinds of algorithms to order-invariant algorithms, and on an appropriate use of the known fact that every free group can be linearly ordered.

We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents’ navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy

$$\mathcal {R} \supset \mathcal {B} \supset \mathcal {P}$$

of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in

$$\mathcal {R}$$

, limited approximability in

$$\mathcal {B}$$

, and tractability in

$$\mathcal {P}$$

. We also give topologies in which DMVP in

$$\mathcal {R}$$

is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.

We present a characterization of the linear rank-width of distance-hereditary graphs. Using the characterization, we show that the linear rank-width of every

$$n$$

-vertex distance-hereditary graph can be computed in time

$$\mathcal {O}(n^2\cdot \log (n))$$

, and a linear layout witnessing the linear rank-width can be computed with the same time complexity. For our characterization, we combine modifications of canonical split decompositions with an idea of [Megiddo, Hakimi, Garey, Johnson, Papadimitriou: The complexity of searching a graph. JACM 1988], used for computing the path-width of trees. We also provide a set of distance-hereditary graphs which contains the set of distance-hereditary vertex-minor obstructions for linear rank-width. The set given in [Jeong, Kwon, Oum: Excluded vertex-minors for graphs of linear rank-width at most k. STACS 2013: 221–232] is a subset of our obstruction set.

We study Vertex Contact representations of Paths on a Grid (VCPG). In such a representation the vertices of

$$G$$

are represented by a family of interiorly disjoint grid-paths. Adjacencies are represented by contacts between an

endpoint

of one grid-path and an

interior point

of another grid-path. Defining

$$u \rightarrow v$$

if the path of

$$u$$

ends on path of

$$v$$

we obtain an orientation on

$$G$$

from a VCPG. To get hand on the bends of the grid path the orientation is not enough. We therefore consider pairs (

$$\alpha ,\psi $$

): a 2-orientation

$$\alpha $$

and a flow

$$\psi $$

in the angle graph. The 2-orientation describes the contacts of the ends of a grid-path and the flow describes the behavior of a grid-path between its two ends. We give a necessary and sufficient condition for such a pair

$$(\alpha ,\psi $$

) to be realizable as a VCPG.

Using realizable pairs we show that every planar (2, 2)-tight graph admits a VCPG with at most 2 bends per path and that this is tight. Using the same we show that simple planar (2, 1)-sparse graphs have a 4-bend representation and simple planar (2, 0)-sparse graphs have 6-bend representation. We do not believe that the latter two are tight, we conjecture that simple planar (2, 0)-sparse graphs have a 3-bend representation.

The paper [J. Balogh, B. Bollobás, D. Weinreich, A jump to the Bell number for hereditary graph properties,

J. Combin. Theory Ser. B

95 (2005) 29–48] identifies a jump in the speed of hereditary graph properties to the Bell number

$$B_n$$

and provides a partial characterisation of the family of minimal classes whose speed is at least

$$B_n$$

. In the present paper, we give a complete characterisation of this family. Since this family is infinite, the decidability of the problem of determining if the speed of a hereditary property is above or below the Bell number is questionable. We answer this question positively for properties defined by finitely many forbidden induced subgraphs. In other words, we show that there exists an algorithm which, given a finite set

$$\mathcal {F}$$

of graphs, decides whether the speed of the class of graphs containing no induced subgraphs from the set

$$\mathcal {F}$$

is above or below the Bell number.

A family

$$\mathcal {F}$$

of permutations of the vertices of a hypergraph

$$H$$

is called

pairwise suitable

for

$$H$$

if, for every pair of disjoint edges in

$$H$$

, there exists a permutation in

$$\mathcal {F}$$

in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for

$$H$$

is called the

separation dimension

of

$$H$$

and is denoted by

$$\pi (H)$$

. Equivalently,

$$\pi (H)$$

is the smallest natural number

$$k$$

so that the vertices of

$$H$$

can be embedded in

$$\mathbb {R}^k$$

such that any two disjoint edges of

$$H$$

can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph

$$H$$

is equal to the

boxicity

of the line graph of

$$H$$

. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension.

An induced matching in a graph is a set of edges whose endpoints induce a

$$1$$

-regular subgraph. It is known that every

$$n$$

-vertex graph has at most

$$10^{n/5}\approx 1.5849^n$$

maximal induced matchings, and this bound is best possible. We prove that every

$$n$$

-vertex triangle-free graph has at most

$$3^{n/3}\approx 1.4423^n$$

maximal induced matchings, and this bound is attained by every disjoint union of copies of the complete bipartite graph

$$K_{3,3}$$

. Our result implies that all maximal induced matchings in an

$$n$$

-vertex triangle-free graph can be listed in time

$$O(1.4423^n)$$

, yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph.

We study the following independent set reconfiguration problem: given two independent sets

$$I$$

and

$$J$$

of a graph

$$G$$

, both of size at least

$$k$$

, is it possible to transform

$$I$$

into

$$J$$

by adding and removing vertices one-by-one, while maintaining an independent set of size at least

$$k$$

throughout? This problem is known to be PSPACE-hard in general. For the case that

$$G$$

is a cograph on

$$n$$

vertices, we show that it can be solved in polynomial time. More generally, we show that for a graph class

$$\mathcal {G}$$

that includes all chordal and claw-free graphs, the problem can be solved in polynomial time for graphs that can be obtained from a collection of graphs from

$$\mathcal {G}$$

using disjoint union and complete join operations.

The boxicity of a graph

$$G$$

is the least integer

$$d$$

such that

$$G$$

has an intersection model of axis-aligned

$$d$$

-dimensional boxes.

Boxicity

, the problem of deciding whether a given graph

$$G$$

has boxicity at most

$$d$$

, is NP-complete for every fixed

$$d \ge 2$$

. We show that

Boxicity

is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al. [

4

], that

Boxicity

is fixed-parameter tractable in the vertex cover number. Moreover, we show that

Boxicity

admits an additive

$$1$$

-approximation when parameterized by the pathwidth of the input graph.

Finally, we provide evidence in favor of a conjecture of Adiga et al. [

4

] that

Boxicity

remains NP-complete even on graphs of constant treewidth.

The class of graphs that do not contain an induced path on

$$k$$

vertices,

$$P_k$$

-free graphs, plays a prominent role in algorithmic graph theory. This motivates the search for special structural properties of

$$P_k$$

-free graphs, including alternative characterizations.

Let

$$G$$

be a connected

$$P_k$$

-free graph,

$$k \ge 4$$

. We show that

$$G$$

admits a connected dominating set whose induced subgraph is either

$$P_{k-2}$$

-free, or isomorphic to

$$P_{k-2}$$

. Surprisingly, it turns out that every minimum connected dominating set of

$$G$$

has this property.

This yields a new characterization for

$$P_k$$

-free graphs: a graph

$$G$$

is

$$P_k$$

-free if and only if each connected induced subgraph of

$$G$$

has a connected dominating set whose induced subgraph is either

$$P_{k-2}$$

-free, or isomorphic to

$$C_k$$

. This improves and generalizes several previous results; the particular case of

$$k=7$$

solves a problem posed by van ’t Hof and Paulusma [A new characterization of

$$P_6$$

-free graphs, COCOON 2008] [

12

].

In the second part of the paper, we present an efficient algorithm that, given a connected graph

$$G$$

, computes a connected dominating set

$$X$$

of

$$G$$

with the following property: for the minimum

$$k$$

such that

$$G$$

is

$$P_k$$

-free, the subgraph induced by

$$X$$

is

$$P_{k-2}$$

-free or isomorphic to

$$P_{k-2}$$

.

As an application our results, we prove that

Hypergraph 2-Colora

bility

, an NP-complete problem in general, can be solved in polynomial time for hypergraphs whose vertex-hyperedge incidence graph is

$$P_7$$

-free.

Planar graphs are known to have geometric representations of various types, e.g. as contacts of disks, triangles or - in the bipartite case - vertical and horizontal segments. It is known that such representations can be drawn in linear time, we here wonder whether it is as easy to decide whether a partial representation can be completed to a representation of the whole graph. We show that in each of the cases above, this problem becomes NP-hard. These are the first classes of geometric graphs where extending partial representations is provably harder than recognition, as opposed to e.g. interval graphs, circle graphs, permutation graphs or even standard representations of plane graphs.

On the positive side we give two polynomial time algorithms for the grid contact case. The first one is for the case when all vertical segments are pre-represented (note: the problem remains NP-complete when a subset of the vertical segments is specified, even if none of the horizontals are). Secondly, we show that the case when the vertical segments have only their

$$x$$

-coordinates specified (i.e., they are ordered horizontally) is polynomially equivalent to level planarity, which is known to be solvable in polynomial time.

In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph

$$D,$$

find a path in

$$D$$

that collects a maximum number of distinct labels. Our main results are a

$$\sqrt{OPT}$$

-approximation algorithm for this problem and a self-reduction showing that any constant ratio approximation algorithm for this problem can be converted into a PTAS. This last result, combined with the

APX

-hardness of the problem, shows that the problem cannot be approximated within a constant ratio unless

$$P=NP$$

.

In the

verification under uncertainty

setting, an algorithm is given, for each input item, an

uncertainty area

that is guaranteed to contain the exact input value, as well as an assumed input value. An

update

of an input item reveals its exact value. If the exact value is equal to the assumed value, we say that the update

verifies

the assumed value. We consider verification under uncertainty for the minimum spanning tree (MST) problem for undirected weighted graphs, where each edge is associated with an uncertainty area and an assumed edge weight. The objective of an algorithm is to compute the smallest set of updates with the property that, if the updates of all edges in the set verify their assumed weights, the edge set of an MST can be computed. We give a polynomial-time optimal algorithm for the MST verification problem by relating the choices of updates to vertex covers in a bipartite auxiliary graph. Furthermore, we consider an alternative uncertainty setting where the vertices are embedded in the plane, the weight of an edge is the Euclidean distance between the endpoints of the edge, and the uncertainty is about the location of the vertices. An update of a vertex yields the exact location of that vertex. We prove that the MST verification problem in this vertex uncertainty setting is NP-hard. This shows a surprising difference in complexity between the edge and vertex uncertainty settings of the MST verification problem.

The weak variant of the Hanani–Tutte theorem says that a graph is planar, if it can be drawn in the plane so that every pair of edges cross an even number of times. Moreover, we can turn such a drawing into an embedding without changing the order in which edges leave the vertices. We prove a generalization of the weak Hanani–Tutte theorem that also easily implies the monotone variant of the weak Hanani–Tutte theorem by Pach and Tóth. Thus, our result can be thought of as a common generalization of these two neat results. In other words, we prove the weak Hanani-Tutte theorem for strip clustered graphs, whose clusters are linearly ordered vertical strips in the plane and edges join only vertices in the same cluster or in neighboring clusters with respect to this order.

Besides usual tools for proving Hanani-Tutte type results our proof combines Hall’s marriage theorem, and a characterization of embedded upward planar digraphs due to Bertolazzi et al.

We study two problems related to the Small Set Expansion Conjecture [

14

]: the

Maximum weight

$$m'$$

-edge cover

(

MWEC

) problem and the

Fixed cost minimum edge cover

(

FCEC

) problem. In the

MWEC

problem, we are given an undirected simple graph

$$G=(V,E)$$

with integral vertex weights. The goal is to select a set

$$U\subseteq V$$

of maximum weight so that the number of edges with at least one endpoint in

$$U$$

is at most

$$m'$$

. Goldschmidt and Hochbaum [

8

] show that the problem is NP-hard and they give a

$$3$$

-approximation algorithm for the problem. The approximation guarantee was improved to

$$2+\epsilon $$

, for any fixed

$$\epsilon > 0$$

[

12

]. We present an approximation algorithm that achieves a guarantee of

$$2$$

. Interestingly, we also show that for any constant

$$\epsilon > 0$$

, a

$$(2-\epsilon )$$

-ratio for

MWEC

implies that the Small Set Expansion Conjecture [

14

] does not hold. Thus, assuming the Small Set Expansion Conjecture, the bound of 2 is tight. In the

FCEC

problem, we are given a vertex weighted graph, a bound

$$k$$

, and our goal is to find a subset of vertices

$$U$$

of total weight at least

$$k$$

such that the number of edges with at least one edges in

$$U$$

is minimized. A

$$2(1+\epsilon )$$

-approximation for the problem follows from the work of Carnes and Shmoys [

3

]. We improve the approximation ratio by giving a

$$2$$

-approximation algorithm for the problem and show a

$$(2-\epsilon )$$

-inapproximability under Small Set Expansion Conjecture conjecture. Only the NP-hardness result was known for this problem [

8

]. We show that a natural linear program for

FCEC

has an integrality gap of

$$2-o(1)$$

. We also show that for any constant

$$\rho >1$$

, an approximation guarantee of

$$\rho $$

for the

FCEC

problem implies a

$$\rho (1+o(1))$$

approximation for

MWEC

. Finally, we define the

Degrees density augmentation

problem which is the density version of the

FCEC

problem. In this problem we are given an undirected graph

$$G=(V,E)$$

and a set

$$U\subseteq V$$

. The objective is to find a set

$$W$$

so that

$$(e(W)+e(U,W))/deg(W)$$

is maximum. This problem admits an LP-based exact solution [

4

]. We give a combinatorial algorithm for this problem.

The Hadwiger number of a graph

$$G$$

is the largest integer

$$h$$

such that

$$G$$

has the complete graph

$$K_h$$

as a minor. We show that the problem of determining the Hadwiger number of a graph is

NP

-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer

$$h$$

such that

$$G$$

has a minor with

$$h$$

vertices and diameter at most

$$s$$

. We show that this problem can be solved in polynomial time on AT-free graphs when

$$s\ge 2$$

, but is

NP

-hard on chordal graphs for every fixed

$$s\ge 2$$

.

A graph

$$G = (V,E)$$

is a

threshold tolerance

graph if each vertex

$$v \in V$$

can be assigned a weight

$$w_v$$

and a tolerance

$$t_v$$

such that two vertices

$$x,y \in V$$

are adjacent if

$$w_x + w_y \ge \min (t_x,t_y)$$

. Currently, the most efficient recognition algorithm for threshold tolerance graphs is the algorithm of Monma, Reed, and Trotter which has an

$$O(n^4)$$

runtime. We give an

$$O(n^2)$$

algorithm for recognizing threshold tolerance and their complements, the co-threshold tolerance (co-TT) graphs, resolving an open question of Golumbic, Weingarten, and Limouzy.

The

Induced Disjoint Paths

problem is to test whether a graph

$$G$$

with

$$k$$

distinct pairs of vertices

$$(s_{i},t_{i})$$

contains paths

$$P_{1},\ldots ,P_{k}$$

such that

$$P_{i}$$

connects

$$s_{i}$$

and

$$t_{i}$$

for

$$i=1,\ldots ,k$$

, and

$$P_{i}$$

and

$$P_{j}$$

have neither common vertices nor adjacent vertices (except perhaps their ends) for

$$1 \le i < j \le k$$

. We present a linear-time algorithm that solves

Induced Disjoint Paths

and finds the corresponding paths (if they exist) on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of

Induced Disjoint Paths

where the pairs

$$(s_{i},t_{i})$$

are not necessarily distinct.

We give constant-factor approximation algorithms for branch-decomposition of planar graphs. Our main result is an algorithm which for an input planar graph

$$G$$

of

$$n$$

vertices and integer

$$k$$

, in

$$O(n\log ^4n)$$

time either constructs a branch-decomposition of

$$G$$

with width at most

$$(2+\delta )k$$

,

$$\delta >0$$

is a constant, or a

$$(k+1)\times \lceil {\frac{k+1}{2}}\rceil $$

cylinder minor of

$$G$$

implying

$${\mathrm{bw}}(G)>k$$

,

$${\mathrm{bw}}(G)$$

is the branchwidth of

$$G$$

. This is the first

$$\tilde{O}(n)$$

time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous

$$\min \{O(n^{1+\epsilon }),O(nk^3)\}$$

(

$$\epsilon >0$$

is a constant) time constant-factor approximations. For a planar graph

$$G$$

and

$$k={\mathrm{bw}}(G)$$

, a branch-decomposition of width at most

$$(2+\delta )k$$

and a

$$g\times \frac{g}{2}$$

cylinder/grid minor with

$$g=\frac{k}{\beta }$$

,

$$\beta >2$$

is constant, can be computed by our algorithm in

$$O(n\log ^4n\log k)$$

time.

In the Directed

$$k$$

-Chinese Postman Problem (

$$k$$

-DCPP), we are given a connected weighted digraph

$$G$$

and asked to find

$$k$$

non-empty closed directed walks covering all arcs of

$$G$$

such that the total weight of the walks is minimum. Gutin, Muciaccia and Yeo (Theor. Comput. Sci.

513

, 124–128 (2013)) asked for the parameterized complexity of

$$k$$

-DCPP when

$$k$$

is the parameter. We prove that the

$$k$$

-DCPP is fixed-parameter tractable.

We also consider a related problem of finding

$$k$$

arc-disjoint directed cycles in an Euler digraph, parameterized by

$$k$$

. Slivkins (ESA 2003) showed that this problem is W[1]-hard for general digraphs. Generalizing another result by Slivkins, we prove that the problem is fixed-parameter tractable for Euler digraphs. The corresponding problem on vertex-disjoint cycles in Euler digraphs remains W[1]-hard even for Euler digraphs.

We introduce the colored decompositions framework, in which vertices of the graph can be equipped with colors, and in which the goal is to find decompositions of this graph that do not separate the color classes. In this paper, we give two linear time algorithms for the colored modular and split decompositions of graphs, and we apply them to give linear time algorithms for the modular and split decompositions of trigraphs, which improves a result of Thomassé, Trotignon and Vuskovic (2013). As a byproduct, we introduce the non-separating families that allow us to prove that those two decompositions have the same properties on graphs and on trigraphs.

The Traveling Salesman Problem is one of the best studied NP-hard problems in combinatorial optimization. Powerful methods have been developed over the last 60 years to find optimum solutions to large TSP instances. The largest TSP instance so far that has been solved optimally has 85,900 vertices. Its solution required more than 136 years of total CPU time using the branch-and-cut based Concorde TSP code [

1

]. In this paper we present graph theoretic results that allow to prove that some edges of a TSP instance cannot occur in any optimum TSP tour. Based on these results we propose a combinatorial algorithm to identify such edges. The runtime of the main part of our algorithm is

$$O(n^2 \log n)$$

for an

$$n$$

-vertex TSP instance. By combining our approach with the Concorde TSP solver we are able to solve a large TSPLIB instance more than 11 times faster than Concorde alone.

The NP-hard

Rainbow Subgraph

problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most

$$k$$

vertices. We examine the parameterized complexity of

Rainbow Subgraph

for paths, trees, and general graphs. We show, for example, APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice. Moreover, we show that

Rainbow Subgraph

is W[1]-hard with respect to the parameter

$$k$$

and also with respect to the dual parameter

$$\ell :=n-k$$

where

$$n$$

is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomial-size problem kernel for the combined parameter

$$\ell $$

and “maximum number of colors incident with any vertex”.

A well-studied problem in phylogenetics is to determine the minimum number of hybridization events necessary to explain conflicts among several evolutionary trees, e.g. from different genes. An evolutionary history with hybridization events (or, more generally, reticulations) can be described by a rooted leaf-labelled directed acyclic graph, which is called a phylogenetic network. The reticulation number of such a phylogenetic network can be defined as the sum of all indegrees minus the number of vertices plus one. The considered problem can now formally be stated as follows. Given a finite set

$$X$$

, a collection

$$\mathcal {T}$$

of rooted phylogenetic trees on

$$X$$

and

$$k\in \mathbb {N}^{+}$$

, the

Hybridization Number

problem asks if there exists a rooted phylogenetic network on

$$X$$

that displays all trees from

$$\mathcal {T}$$

and has reticulation number at most

$$k$$

. We show that

Hybridization Number

admits a kernel of size

$$4k(5k)^t$$

if

$$\mathcal {T}$$

contains

$$t$$

(not necessarily binary) rooted phylogenetic trees. In addition, we show a slightly different kernel of size

$$20k^2(\varDelta ^+-1)$$

with

$$\varDelta ^+$$

the maximum outdegree of the input trees.

We present an approach for the traveling salesman problem with graph metric based on Steiner cycles. A Steiner cycle is a cycle that is required to contain some specified subset of vertices. For a graph

$$G$$

, if we can find a spanning tree

$$T$$

and a simple cycle that contains the vertices with odd-degree in

$$T$$

, then we show how to combine the classic “double spanning tree” algorithm with Christofides’ algorithm to obtain a TSP tour of length at most

$$\frac{4n}{3}$$

. We use this approach to show that a graph containing a Hamiltonian path has a TSP tour of length at most

$$4n/3$$

.

Since a Hamiltonian path is a spanning tree with two leaves, this motivates the question of whether or not a graph containing a spanning tree with few leaves has a short TSP tour. The recent techniques of Mömke and Svensson imply that a graph containing a depth-first-search tree with

$$k$$

leaves has a TSP tour of length

$$4n/3 + O(k)$$

. Using our approach, we can show that a

$$2(k-1)$$

-vertex connected graph that contains a spanning tree with at most

$$k$$

leaves has a TSP tour of length

$$4n/3$$

. We also explore other conditions under which our approach results in a short tour.

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half-open unit intervals of the real line. This is a proper superclass of the well known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach and Szwarcfiter (Mixed unit interval graphs. Discrete Math.

312

, 3357–3363 (2012)). Our characterization also leads to a polynomial-time recognition algorithm for mixed unit interval graphs.

A set of vertices in a graph is

connected

if the set induces a connected subgraph. Using Shearer’s entropy lemma, we show that the number of connected sets in an

$$n$$

-vertex graph with maximum vertex degree

$$d$$

is

$$O(1.9351^n)$$

for

$$d=3$$

,

$$O(1.9812^n)$$

for

$$d=4$$

, and

$$O(1.9940^n)$$

for

$$d=5$$

. Dually, we construct infinite families of generalized ladder graphs whose number of connected sets is bounded from below by

$$\varOmega (1.5537^n)$$

for

$$d=3$$

,

$$\varOmega (1.6180^n)$$

for

$$d=4$$

, and

$$\varOmega (1.7320^n)$$

for

$$d=5$$

.

We study the parameterized complexity of the classical

Edge Hamiltonian Path

problem and give several fixed-parameter tractability results. First, we settle an open question of Demaine et al. by showing that

Edge Hamiltonian Path

is FPT parameterized by vertex cover, and that it also admits a cubic kernel. We then show fixed-parameter tractability even for a generalization of the problem to arbitrary hypergraphs, parameterized by the size of a (supplied) hitting set. We also consider the problem parameterized by treewidth or clique-width. Surprisingly, we show that the problem is FPT for both of these standard parameters, in contrast to its vertex version, which is W[1]-hard for clique-width. Our technique, which may be of independent interest, relies on a structural characterization of clique-width in terms of treewidth and complete bipartite subgraphs due to Gurski and Wanke.

The square of a graph

$$G$$

, denoted

$$G^2$$

, is obtained from

$$G$$

by putting an edge between two distinct vertices whenever their distance is two. Then

$$G$$

is called a square root of

$$G^2$$

. Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a chordal graph or even a split graph.

We present a polynomial time algorithm that decides whether a given graph has a ptolemaic square root. If such a root exists, our algorithm computes one with a minimum number of edges.

In the second part of our paper, we give a characterization of the graphs that admit a 3-sun-free split square root. This characterization yields a polynomial time algorithm to decide whether a given graph has such a root, and if so, to compute one.

In

$$2$$

-neighbourhood bootstrap percolation on a graph

$$G$$

, an infection spreads according to the following deterministic rule: infected vertices of

$$G$$

remain infected forever and in consecutive rounds healthy vertices with at least

$$2$$

already infected neighbours become infected. Percolation occurs if eventually every vertex is infected. The maximum time

$$t(G)$$

is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved [

7

] that deciding if

$$t(G)\ge k$$

is polynomial time solvable for

$$k=2$$

, but is NP-Complete for

$$k=4$$

and is NP-Complete if the graph is bipartite and

$$k=7$$

. In this paper, we solve the open questions. Let

$$n = |V(G)|$$

and

$$m = |E(G)|$$

. We obtain an

$$\varTheta (m n^5)$$

-time algorithm to decide if

$$t(G)\ge 3$$

in general graphs. In bipartite graphs, we obtain an

$$\varTheta (m n^3)$$

-time algorithm to decide if

$$t(G)\ge 3$$

and an

$$O(m n^{13})$$

-time algorithm to decide if

$$t(G)\ge 4$$

. We also prove that deciding if

$$t(G)\ge 5$$

is NP-Complete in bipartite graphs.

We study a broad class of graph partitioning problems, where each problem is specified by a graph

$$G=(V,E)$$

, and parameters

$$k$$

and

$$p$$

. We seek a subset

$$U\subseteq V$$

of size

$$k$$

, such that

$$\alpha _1m_1 + \alpha _2m_2$$

is at most (or at least)

$$p$$

, where

$$\alpha _1,\alpha _2\in \mathbb {R}$$

are constants defining the problem, and

$$m_1, m_2$$

are the cardinalities of the edge sets having both endpoints, and exactly one endpoint, in

$$U$$

, respectively. This class of

fixed-cardinality graph partitioning problems (FGPPs)

encompasses

Max

$$(k,n-k)$$

-

Cut

,

Min

$$k$$

-

Vertex Cover

,

$$k$$

-

Densest Subgraph

, and

$$k$$

-

Sparsest Subgraph

.

Our main result is an

$$O^*(4^{k+o(k)}\varDelta ^k)$$

algorithm for any problem in this class, where

$$\varDelta \ge 1$$

is the maximum degree in the input graph. This resolves an open question posed by Bonnet et al. [IPEC 2013]. We obtain faster algorithms for certain subclasses of FGPPs, parameterized by

$$p$$

, or by

$$(k+p)$$

. In particular, we give an

$$O^*(4^{p+o(p)})$$

time algorithm for

Max

$$(k,n-k)$$

-

Cut

, thus improving significantly the best known

$$O^*(p^p)$$

time algorithm.

Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems

MaxCut

,

Graph Coloring

,

Hamiltonian Cycle

and

Edge Dominating Set

that are all FPT parameterized by treewidth but none of which can be FPT parameterized by clique-width unless the Exponential Time Hypothesis fails, as shown by Fomin et al. [

7

]. We therefore seek a structural graph parameter that shares some of the generality of clique-width without paying this price.

Based on splits, branch decompositions and the work of Vatshelle [

16

] on Maximum Matching-width, we consider the graph parameter sm-width which lies between treewidth and clique-width. Some graph classes of unbounded tree-width, like distance-hereditary graphs, have bounded sm-width. We show that

MaxCut

,

Graph Coloring

,

Hamiltonian Cycle

and

Edge Dominating Set

are all FPT parameterized by sm-width.

The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of size

$$k$$

, when

$$k$$

is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size

$$k$$

. A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size

$${O}(k^5)$$

. All our results rely on a decomposition theorem of bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.