Exact and approximation algorithms for covering timeline in temporal graphs
研究时间图上的顶点覆盖变体问题，用于总结时间图中的时间线活动。证明了问题NP难，给出了近似比为O(T log n)的算法，并对每个时间戳最多一条时间边的特例给出了4(T-1)近似算法和参数化算法。
Abstract We consider a variant of vertex cover on temporal graphs that has been recently defined for summarization of timeline activities in temporal graphs. The problem has been proved to be NP-hard, even for several restrictions of the time domain and vertex degree. We present novel algorithmic contributions for the problem and we give an approximation algorithm of factor $$O(T \log {n})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , on a temporal graph of T timestamps and n vertices. We focus then on the NP-hard restriction of the problem, where at most one temporal edge is defined in each timestamp. For this restriction we present a $$4(T-1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>4</mml:mn> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> approximation algorithm and a parameterized algorithm (a reduction to kernel) for parameter the cost, called span, of the solution.