C.E. Groenland
35 records found
1
Given an integer n, let G(n) be the number of integer sequences n − 1 ≥ d1 ≥ d2 ≥ · · · ≥ dn ≥ 0 that are the degree sequence of some graph. We show that G(n) = (c + o(1))4n/n3/4 for some constant c > 0, improvi
...
We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively, states that all connected vertex-transitive graphs contain a Hamiltonian path, and that all suffici
...
Given access to the vertex set (Formula presented.) of a connected graph (Formula presented.) and an oracle that given two vertices (Formula presented.), returns the shortest path distance between (Formula presented.) and (Formula presented.), how many queries are needed to recon
...
We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that,
...
We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in O(n4) time, where n denotes the number of
...
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V (G) to V (H). In the graph homomorphism problem, denoted by Hom(H), the graph H is fixed and we need to determine if there exists a homomorphism from an instance graph G to H. We study the complexity
...
Given a finite poset P, we say that a family F of subsets of [n] is P-saturated if F does not contain an induced copy of P, but adding any other set to F creates an induced copy of P. The induced saturation number of P, denoted by sat∗(n,P), is the size of the smallest
...
In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices u and v, the oracle returns the shortest path distance between u and v in the graph. The length of a tree decompo
...
Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as LIST
...
An independent transversal of a graph (Formula presented.) with a vertex partition (Formula presented.) is an independent set of (Formula presented.) intersecting each block of (Formula presented.) in a single vertex. Wanless and Wood proved that if each block of (Formula present
...
Two permutations σ and π are ℓ-similar if they can be decomposed into subpermutations σ(1), . . . ,σ(ℓ) and π(1), . . . ,π(ℓ) such that σ(i) is order-isomorphic to π(i) for all i ∈[ℓ]. Recently, Dudek, Grytczuk, and Ruciński Variations on twins in permutations, Electron. J. Combi
...
We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In general, different (labelled) graphs may have the same set of connected triples, making unique reco
...
A classic model to study strategic decision making in multi-agent systems is the normal-form game. This model can be generalised to allow for an infinite number of pure strategies leading to continuous games. Multi-objective normal-form games are another generalisation that model
...
We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of (t√log t) This is the first algorithm to achieve an f(t)-approximation for some function f. Our approach builds on the following key insight: ever
...
Parameterized Complexity of Binary CSP
Vertex Cover, Treedepth, and Related Parameters
We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: Binary CSP parameterized by the vertex
...
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture
...
We show that List Colouring can be solved on n-vertex trees by a deterministic Turing machine using O(log n) bits on the worktape. Given an n-vertex graph G = (V,E) and a list L(v) ⊆ {1, . . . , n} of available colours for each v ∈ V , a list colouring for G is a proper colouring
...
The deck of a graph G is the multiset of cards {G−v:v∈V(G)}. Myrvold (1992) showed that the degree sequence of a graph on n≥7 vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree d can be reconstructed from
...
We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that,
...
In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)nO(1) time and f(k) log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only t
...