Source author record

Janka Chlebíková

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

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Computational Complexity math.CO

Catalog footprint

Research overview

2works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

Proportionally dense subgraph of maximum size: complexity and approximation

We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is APX-hard on split graphs, and NP-hard on bipartite graphs. We also show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs. Nevertheless, we present a simple polynomial-time $(2-\frac{2}{Δ+1})$ -approximation algorithm for the problem, where $Δ$ is the maximum degree of the graph. Finally, we show that all Hamiltonian cubic graphs with $n$ vertices (except two) have a PDS of size $\lfloor \frac{2n+1}{3} \rfloor$ , which we prove to be an upper bound on the size of a PDS in cubic graphs.

preprint2014arXiv

The Firefighter Problem: A Structural Analysis

We consider the complexity of the firefighter problem where b>=1 firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al.,2007) and on trees of bounded degree b+3 for any fixed budget b>=2 (Bazgan et al.,2012). In this paper, we provide further insight into the complexity landscape of the problem by showing that the pathwidth and the maximum degree of the input graph govern its complexity. More precisely, we first prove that the problem is NP-complete even on trees of pathwidth at most three for any fixed budget b>=1. We then show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter "pathwidth" and "maximum degree" of the input graph.

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.