Researcher profile

Istvan Miklos

Istvan Miklos contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

math.CO Computational Complexity Computational Engineering, Finance, and Science

Trust snapshot

Quick read

Trust 15 - Baseline

3works

0followers

3topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

preprint2021arXiv

Counting Maximum Matchings in Planar Graphs Is Hard

Here we prove that counting maximum matchings in planar, bipartite graphs is #P-complete. This is somewhat surprising in the light that the number of perfect matchings in planar graphs can be computed in polynomial time. We also prove that counting non-necessarily perfect matchings in planar graphs is already #P-complete if the problem is restricted to bipartite graphs. So far hardness was proved only for general, non-necessarily bipartite graphs.

preprint2016arXiv

Half-regular factorizations of the complete bipartite graph

We consider a bipartite version of the color degree matrix problem. A bipartite graph $G(U,V,E)$ is half-regular if all vertices in $U$ have the same degree. We give necessary and sufficient conditions for a bipartite degree matrix (also known as demand matrix) to be the color degree matrix of an edge-disjoint union of half-regular graphs. We also give necessary and sufficient perturbations to transform realizations of a half-regular degree matrix into each other. Based on these perturbations, a Markov chain Monte Carlo method is designed in which the inverse of the acceptance ratios are polynomial bounded. Realizations of a half-regular degree matrix are generalizations of Latin squares, and they also appear in applied neuroscience.

preprint2013arXiv

On sampling SCJ rearrangement scenarios

The Single Cut or Join (SCJ) operation on genomes, generalizing chromosome evolution by fusions and fissions, is the computationally simplest known model of genome rearrangement. While most genome rearrangement problems are already hard when comparing three genomes, it is possible to compute in polynomial time a most parsimonious SCJ scenario for an arbitrary number of genomes related by a binary phylogenetic tree. Here we consider the problems of sampling and counting the most parsimonious SCJ scenarios. We show that both the sampling and counting problems are easy for two genomes, and we relate SCJ scenarios to alternating permutations. However, for an arbitrary number of genomes related by a binary phylogenetic tree, the counting and sampling problems become hard. We prove that if a Fully Polynomial Randomized Approximation Scheme or a Fully Polynomial Almost Uniform Sampler exist for the most parsimonious SCJ scenario, then RP = NP. The proof has a wider scope than genome rearrangements: the same result holds for parsimonious evolutionary scenarios on any set of discrete characters.