5 papers · 1 filter
NP-Hardness and a PTAS for Maximum Interval Multicover, with Applications to Dense Subgraphs
Morteza Alimi, Tobias Mömke, Alexandru Popa +1
Given intervals and points on a line, each point with a demand, and a budget , Maximum Interval Multicover asks for at most intervals that satisfy as many points as possible…
Structural Complexity of Matching-Match: Dense and Sparse Graphs
Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We st…
An Approximation Algorithm for Non-uniform Non-contiguous Translocation Distance
Maria Constantin, Adrian Miclăuş, Alexandru Popa
Translocations are genome rearrangement operations that exchange prefixes of two chromosomes. We study the non-uniform non-contiguous translocation distance problem, where every st…
Colored Interaction-Profile Realization: Complexity of Matching-Match on Spiders
Ilie Dumitru, Adrian Miclaus, Alexandru Popa
Network motifs and colored local interaction patterns provide a useful way to describe the structure of complex networks. Motivated by an inverse realization perspective, we study…
Maximum Matching-Match: Hardness and Approximation
Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
In this paper, we study \textsc{MaxMMP}, an optimization variant of the Matching-Match Puzzle introduced by Iburi and Uehara (FUN 2024). Given a graph, a partial vertex coloring, a…