Document Open Access Logo

Temporal Unit Interval Independent Sets

Authors Danny Hermelin, Yuval Itzhaki, Hendrik Molter, Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.19.pdf
  • Filesize: 0.72 MB
  • 16 pages

Document Identifiers

Author Details

Danny Hermelin
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Yuval Itzhaki
  • Faculty IV, Algorithmics and Computational Complexity, TU Berlin, Germany
Hendrik Molter
  • Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Rolf Niedermeier
  • Faculty IV, Algorithmics and Computational Complexity, TU Berlin, Germany

Funding

D. Hermelin and H. Molter are supported by the ISF, grant No. 1070/20.

Acknowledgements

The authors want to thank anonymous SAND reviewers for their constructive comments.

Cite AsGet BibTex

Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Rolf Niedermeier. Temporal Unit Interval Independent Sets. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.19

Abstract

Temporal graphs have been recently introduced to model changes to a given network that occur throughout a fixed period of time. We introduce and investigate the Temporal Δ Independent Set problem, a temporal variant of the well known Independent Set problem. This problem is e.g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (changing) constraints on each day they need to be performed. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a day if their time-intervals overlap on that day. This leads us to considering Temporal Δ Independent Set on the restricted class of temporal unit interval graphs, i.e., temporal graphs where each layer is unit interval. We present several hardness results for this problem, as well as two algorithms: The first is a constant-factor approximation algorithm for instances where τ, the total number of time steps (layers) of the temporal graph, and Δ, a parameter that allows us to model some tolerance in the conflicts, are constants. For the second result we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. We provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Discrete mathematics
Keywords
  • Temporal Graphs
  • Vertex Orderings
  • Order Preservation
  • Interval Graphs
  • Algorithms and Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Karhan Akcoglu, James Aspnes, Bhaskar DasGupta, and Ming-Yang Kao. Opportunity cost algorithms for combinatorial auctions. In Computational Methods in Decision-Making, Economics and Finance, pages 455-479. Springer, 2002. Google Scholar
  2. Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zamaraev. Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107:108-123, 2020. Google Scholar
  3. Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, and Irina Shapira. Scheduling split intervals. SIAM Journal on Computing, 36(1):1-15, 2006. Google Scholar
  4. Matthias Bentert, Anne-Sophie Himmel, Hendrik Molter, Marco Morik, Rolf Niedermeier, and René Saitenmacher. Listing all maximal k-plexes in temporal graphs. Journal of Experimental Algorithmics (JEA), 24:1-27, 2019. Google Scholar
  5. Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13(3):335-379, 1976. Google Scholar
  6. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. Google Scholar
  7. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178-189, 2003. Google Scholar
  8. Miroslav Chlebík and Janka Chlebíková. Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), pages 267-276. SIAM, 2005. Google Scholar
  9. Michael Dom, Jiong Guo, and Rolf Niedermeier. Approximation and fixed-parameter algorithms for consecutive ones submatrix problems. Journal of Computer and System Sciences, 76(3-4):204-221, 2010. Google Scholar
  10. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. Google Scholar
  11. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34(6):1302-1323, 2005. Google Scholar
  12. Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53-61, 2009. Google Scholar
  13. Paola Flocchini, Bernard Mans, and Nicola Santoro. On the exploration of time-varying networks. Theoretical Computer Science, 469:53-68, 2013. Google Scholar
  14. Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806:197-218, 2020. Google Scholar
  15. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. Google Scholar
  16. Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47-56, 1974. Google Scholar
  17. Paul C. Gilmore and Alan J. Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics, 16:539-548, 1964. Google Scholar
  18. Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC '04), pages 162-173. Springer, 2004. Google Scholar
  19. András Gyárfás and Douglas West. Multitrack interval graphs. Congressus Numerantium 109, 1995. Google Scholar
  20. Mohammad Taghi Hajiaghayi and Yashar Ganjali. A note on the consecutive ones submatrix problem. Information processing letters, 83(3):163-166, 2002. Google Scholar
  21. György Hajós. Über eine Art von Graphen. Internationale Mathematische Nachrichten, 11(65), 1957. Google Scholar
  22. Monika Henzinger, Stefan Neumann, and Andreas Wiese. Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles. In Proceedings of the 36th International Symposium on Computational Geometry (SoCG '20), volume 164 of LIPIcs, pages 51:1-51:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  23. Anne-Sophie Himmel, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge. Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Social Network Analysis and Mining, 7(1):35:1-35:16, 2017. Google Scholar
  24. Wen-Lian Hsu and Jeremy P. Spinrad. Independent sets in circular-arc graphs. Journal of Algorithms, 19(2):145-160, 1995. Google Scholar
  25. Minghui Jiang. On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theoretical Computer Science, 411(49):4253-4262, 2010. Google Scholar
  26. Deborah Joseph, Joao Meidanis, and Prasoon Tiwari. Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. In Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory (SWAT '92), pages 326-337. Springer, 1992. Google Scholar
  27. Richard M Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103. Springer, 1972. Google Scholar
  28. Sanjeev Khanna, Shan Muthukrishnan, and Mike Paterson. On approximating rectangle tiling and packing. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, volume 95, page 384. SIAM, 1998. Google Scholar
  29. Vassilis Kostakos. Temporal graphs. Physica A: Statistical Mechanics and its Applications, 388(6):1007-1023, 2009. Google Scholar
  30. Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining, 8(1):61:1-61:29, 2018. Google Scholar
  31. Dániel Marx. Efficient approximation schemes for geometric problems? In Proceedings of the 13th Annual European Symposium on Algorithms (ESA '05), pages 448-459. Springer, 2005. Google Scholar
  32. George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing maximum matchings in temporal graphs. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS '20), volume 154 of LIPIcs, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  33. George B. Mertzios, Hendrik Molter, and Viktor Zamaraev. Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120:97-115, 2021. Google Scholar
  34. Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239-280, 2016. Google Scholar
  35. N.S. Narayanaswamy and R. Subashini. Obtaining matrices with the consecutive ones property by row deletions. Algorithmica, 71(3):758-773, 2015. Google Scholar
  36. Fred S. Roberts. Indifference graphs. Proof techniques in graph theory. In Proceedings of the Second Ann Arbor Graph Conference, Academic Press, New York, 1969. Google Scholar
  37. Donald J. Rose, Robert Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266-283, 1976. Google Scholar
  38. Alan Tucker. A structure theorem for the consecutive 1’s property. Journal of Combinatorial Theory, Series B, 12(2):153-162, 1972. Google Scholar
  39. Tiphaine Viard, Matthieu Latapy, and Clémence Magnien. Computing maximal cliques in link streams. Theoretical Computer Science, 609:245-252, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact