Algorithmica

In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Directed Feedback Arc Set. In our generalization, we ...$\mathrm{}\mathrm{}$${}_{\mathrm{}}{}_{\mathrm{}}{}_{}$$\mathrm{}\mathrm{}$$\mathrm{}$${}_{}$${}_{}{}_{}$$\mathrm{}$$\mathrm{}$${}_{\mathrm{}}{}_{}$$$

We investigate the problem of computing the number of linear extensions of a given n-element poset whose cover graph has treewidth t. We present an algorithm that runs in time $\tilde{O}(n^{t+3})$ for any constant t; the notation $\tilde{O}$ hides polylogarithmic ...

The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be $\mathsf{NP}$-complete in general, and in practice a range of ...$\mathsf{}$

We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, ...$$

Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a meta-problem may be of main interest. We introduce here a promising ...$$${\mathrm{}}^{\sqrt{}}$${\mathrm{}}^{}$$\mathsf{}\mathrm{}\mathsf{}\mathrm{}$${\mathrm{}}^{\mathcal{}}{}^{\mathcal{}\mathrm{}}$${\mathrm{}}^{}$

We investigate the problem $\#\mathsf{IndSub}(\Phi )$ of counting all induced subgraphs of size k in a graph G that satisfy a given property $\Phi$. This continues the work of Jerrum and Meeks who proved the problem to be $\#\mathrm{W}[1]$-hard for some families of properties ...$$$\mathsf{}$$\mathrm{}\mathrm{}$$$$\mathsf{}$$\mathsf{}$$\mathrm{}\mathrm{}$$$$\mathrm{}$$\mathsf{}$${}^{}$$\mathsf{}$$\mathrm{}\mathrm{}$$$$$

We show that the eccentricities, diameter, radius, and Wiener index of an undirected n-vertex graph with nonnegative edge lengths can be computed in time $O(n·\left(\begin{array}{c}k+\lceil logn\rceil \\ k\end{array}\right)·2^{k}logn)$, where k is linear in the treewidth of the graph. For every $ϵ>0$, this ...${}^{\mathrm{}}$${}^{}$$\left(\begin{array}{c}\\ \end{array}\right)$

Given a graph G, a properk-coloring of G is a partition $c={(S_i)}_{i\in [1,k]}$ of V(G) into k stable sets $S_1,\dots ,S_k$. Given a weight function $w:V(G)\to {\mathbb{R}}^{+}$, the weight of a color$S_i$ is defined as $w(i)={max}_{v\in S_i}w(v)$ and the weight of a coloringc as $w(c)={\sum }_{i=1}^{k}w(i)$. ...$$$$${}^{}$${}_{}$${\mathrm{}}^{\mathcal{}}{}^{\mathcal{}\mathrm{}}$${\mathrm{}}^{}{}^{\mathcal{}\mathrm{}}$${\mathrm{}}^{}{}^{\mathcal{}\mathrm{}}$${\mathrm{}}^{\mathrm{}}\mathrm{}\mathrm{}$$\mathsf{}\mathsf{}\mathsf{}$

The k-leaf power graph G of a tree T is a graph whose vertices are the leaves of T and whose edges connect pairs of leaves at unweighted distance at most k in T. Recognition of the k-leaf power graphs for $k\ge 7$ is still an open problem. In this ...${}_{\mathrm{}}$

In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs H, we study its ...${}_{\mathrm{}\mathrm{}}$${}_{\mathrm{}}$