Source author record

Nikola Yolov

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

ResearcherUnclaimed source record

math.CO Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

4works

3topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Blocker size via matching minors

Finding the maximum number of maximal independent sets in an $n$ -vertex graph $G$ , $i(G)$ , from a restricted class is an extensively studied problem. Let $kK_2$ denote the matching of size $k$ , that is a graph with $2k$ vertices and $k$ disjoint edges. A graph with an induced copy of $kK_2$ contains at least $2^k$ maximal independent sets. The other direction was established in a series of papers finally yielding $i(G) \le (n/k)^{2k}$ for a graph $G$ without an induced $(k+1)K_2$ . Alekseev proved that $i(G)$ is at most the number of induced matchings of $G$ . This work generalises the aforementioned results to clutters. The right substructures in this setting are minors rather than induced subgraphs. Maximal independent sets of a clutter $\mathcal{H}$ are in one-to-one correspondence to the sets of its blocker, $b(\mathcal{H})$ , hence $i(\mathcal{H}) = |b(\mathcal{H})|$ . We show that $|b(\mathcal{H})| \le \sum_{m=0}^{k \cdot f(r)}{|\mathcal{H}| \choose m} {r \choose 2}^m$ for a $(k+1)K_2$ -minor-free clutter $\mathcal{H}$ where $f(r) = (2r-3)2^{r-2}$ and $r$ is the maximum size of a set in $\mathcal{H}$ . A key step in the proofs is, similarly to Alekseev's result, showing that $i(\mathcal{H})$ is bounded by the number of a substructure called semi-matching, and then proving a dependence between the number of semi-matchings and the number of minor matchings. Note that similarly to graphs, a clutter containing a $kK_2$ minor has at least $2^k$ maximal independent sets. From a computational perspective, a polynomial number of independent sets is particularly interesting. Our results lead to polynomial algorithms for restricted instances of many problems including Set Cover and k-SAT.

preprint2016arXiv

Hamilton cycles, minimum degree and bipartite holes

We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large ``bipartite hole`` (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvátal and Erdős. In detail, an $(s, t)$ -bipartite-hole in a graph $G$ consists of two disjoint sets of vertices $S$ and $T$ with $|S|= s$ and $|T|=t$ such that there are no edges between $S$ and $T$ ; and $\widetildeα(G)$ is the maximum integer $r$ such that $G$ contains an $(s, t)$ -bipartite-hole for every pair of non-negative integers $s$ and $t$ with $s + t = r$ . Our central theorem is that a graph $G$ with at least $3$ vertices is Hamiltonian if its minimum degree is at least $\widetildeα(G)$ . From the proof we obtain a polynomial time algorithm that either finds a Hamilton cycle or a large bipartite hole. The theorem also yields a condition for the existence of $k$ edge-disjoint Hamilton cycles. We see that for dense random graphs $G(n,p)$ , the probability of failing to contain many edge-disjoint Hamilton cycles is $(1 - p)^{(1 + o(1))n}$ . Finally, we discuss the complexity of calculating and approximating $\widetildeα(G)$ .

preprint2016arXiv

Polarity and Monopolarity of $3$ -colourable comparability graphs

We sharpen the result that polarity and monopolarity are NP-complete problems by showing that they remain NP-complete if the input graph is restricted to be a $3$ -colourable comparability graph. We start by presenting a construction reducing $1$ - $3$ -SAT to monopolarity of $3$ -colourable comparability graphs. Then we show that polarity is at least as hard as monopolarity for input graphs restricted to a fixed disjoint-union-closed class. We conclude the paper by stating that both polarity and monopolarity of $3$ -colourable comparability graphs are NP-complete problems.

preprint2016arXiv

Recognition of unipolar and generalised split graphs

A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar partition of a graph can be used to find efficiently the clique number, the stability number, the chromatic number, and to solve other problems that are hard for general graphs. We present the first $O(n^2)$ time algorithm for recognition of $n$ -vertex unipolar and generalised split graphs, improving on previous $O(n^3)$ time algorithms.

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.

Nikola Yolov

Research overview

Is this your work?

4 publications

Blocker size via matching minors

Hamilton cycles, minimum degree and bipartite holes

Polarity and Monopolarity of $3$ -colourable comparability graphs

Recognition of unipolar and generalised split graphs

See the researcher in context

Building this map preview

Nikola Yolov

Research overview

Is this your work?

4 publications

Blocker size via matching minors

Hamilton cycles, minimum degree and bipartite holes

Polarity and Monopolarity of 333-colourable comparability graphs

Recognition of unipolar and generalised split graphs

See the researcher in context

Building this map preview

Polarity and Monopolarity of $3$ -colourable comparability graphs