Source author record

Siani Smith

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Discrete Mathematics Data Structures and Algorithms math.CO

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Induced Disjoint Paths and Connected Subgraphs for $H$ -Free Graphs

Paths $P_1,\ldots, P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P_i$ such that each $P_i$ starts from $s_i$ and ends at $t_i$ . This is a classical graph problem that is NP-complete even for $k=2$ . We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

preprint2022arXiv

Partitioning H-Free Graphs of Bounded Diameter

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of $H$ -free graphs, that is, graphs that do not contain some graph $H$ as an induced subgraph, have proven to be an ideal testbed for such a complexity study. However, if the forbidden graph $H$ contains a cycle or claw, then these problems often stay NP-complete. A recent complexity study on the $k$ -Colouring problem shows that we may still obtain tractable results if we also bound the diameter of the $H$ -free input graph. We continue this line of research by initiating a complexity study on the impact of bounding the diameter for a variety of classical vertex partitioning problems restricted to $H$ -free graphs. We prove that bounding the diameter does not help for Independent Set, but leads to new tractable cases for problems closely related to 3-Colouring. That is, we show that Near-Bipartiteness, Independent Feedback Vertex Set, Independent Odd Cycle Transversal, Acyclic 3-Colouring and Star 3-Colouring are all polynomial-time solvable for chair-free graphs of bounded diameter. To obtain these results we exploit a new structural property of 3-colourable chair-free graphs.

preprint2022arXiv

The complexity of L(p,q)-Edge-Labelling

We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially classified. We complete this study for all nonnegative p and q, by showing that, whenever (p,q) is not (0,0), L(p,q)-Edge-Labelling problem is NP-complete. We do this by proving that for all nonnegative p and q, except p=q=0, there exists an integer k so that L(p,q)-Edge-k-Labelling is NP-complete.

preprint2021arXiv

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

For $k\geq 1$ , a $k$ -colouring $c$ of $G$ is a mapping from $V(G)$ to $\{1,2,\ldots,k\}$ such that $c(u)\neq c(v)$ for any two non-adjacent vertices $u$ and $v$ . The $k$ -Colouring problem is to decide if a graph $G$ has a $k$ -colouring. For a family of graphs ${\cal H}$ , a graph $G$ is ${\cal H}$ -free if $G$ does not contain any graph from ${\cal H}$ as an induced subgraph. Let $C_s$ be the $s$ -vertex cycle. In previous work (MFCS 2019) we examined the effect of bounding the diameter on the complexity of $3$ -Colouring for $(C_3,\ldots,C_s)$ -free graphs and $H$ -free graphs where $H$ is some polyad. Here, we prove for certain small values of $s$ that $3$ -Colouring is polynomial-time solvable for $C_s$ -free graphs of diameter $2$ and $(C_4,C_s)$ -free graphs of diameter $2$ . In fact, our results hold for the more general problem List $3$ -Colouring. We complement these results with some hardness result for diameter $4$ .

preprint2021arXiv

QCSP on Reflexive Tournaments

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H_1,...,H_n so that there exists an edge from every vertex of H_i to every vertex of H_j if and only if i<j. We prove that if H has both its initial and final strongly connected component (possibly equal) of size 1, then QCSP(H) is in NL and otherwise QCSP(H) is NP-hard.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Siani Smith

Research overview

Is this your work?

5 publications

Induced Disjoint Paths and Connected Subgraphs for $H$ -Free Graphs

Partitioning H-Free Graphs of Bounded Diameter

The complexity of L(p,q)-Edge-Labelling

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

QCSP on Reflexive Tournaments

See the researcher in context

Building this map preview

Siani Smith

Research overview

Is this your work?

5 publications

Induced Disjoint Paths and Connected Subgraphs for HHH-Free Graphs

Partitioning H-Free Graphs of Bounded Diameter

The complexity of L(p,q)-Edge-Labelling

Colouring Graphs of Bounded Diameter in the Absence of Small Cycles

QCSP on Reflexive Tournaments

See the researcher in context

Building this map preview

Induced Disjoint Paths and Connected Subgraphs for $H$ -Free Graphs