The maximum clique problem (MCP) is to determine in a graph a clique (ie, a complete
subgraph) of maximum cardinality. The MCP is notable for its capability of modeling other …

As a well-known NP-hard problem, the vertex cover problem has broad applications, which
has aroused the concern of many researchers. In recent years, its related optimization …

We present a series of almost settled inapproximability results for three fundamental
problems. The first in our series is the subexponential-time inapproximability of the …

We address the max min vertex cover problem, which is the maximization version of the well
studied min independent dominating set problem, known to be NP-hard and highly …

To ensure robustness in wireless networks, monitoring the network state, performance and
functioning of the nodes and links is crucial, especially for critical applications. This paper …

Fixed-parameter algorithms, approximation algorithms and moderately exponential
algorithms are three major approaches to algorithm design. While each of them being very …

We first devise a branching algorithm that computes a minimum independent dominating set
with running time O∗(1.3351 n)= O∗(20.417 n) and polynomial space. This improves upon …

The parameterized complexity of problems is often studied with respect to the size of their
optimal solutions. However, for a maximization problem, the size of the optimal solution can …

The goal of this paper is to understand how exponential-time approximation algorithms can
be obtained from existing polynomial-time approximation algorithms, existing parameterized …

For any $\varepsilon> 0$, we give a polynomial-time $ n^\varepsilon $-approximation
algorithm for Max Independent Set in graphs of bounded twin-width given with an $ O (1) …