Kernelization and the Larger Picture of Practical ...

Kernelization and the Larger Picture of Practical ...

Kernelization and the Larger Picture of Practical Algorithmics, in Contemporary Context Michael R. Fellows Charles Darwin University Australia WorKer, Vienna 2011 Two thoughts on parameterized complexity and theoretical computer science. (1)PC is as much about workflow reform as

about more fine-grained complexity analysis (2) We want to create mathematical tools with Explanatory Predictive Engineering Three kinds of power To help us create useful algorithms.

A classic example of explanatory power: TYPE CHECKING in ML Combinatorial optimization problems arise frequently in computational molecular biology Except in rare cases, the problems are NP-hard, and the performance guarantees provided by polynomial-time approximation algorithms are far too pessimistic to be useful. Average-case analysis of algorithms is also of limited use because the spectrum of reallife problem instances is unlikely to be representable by a mathematically tractable probablility distribution. Thus it

appears necessary to attack these problems using heuristic algorithms. Although we focus here on computational biology, heuristics are also likely to be the method of choice in many other application areas, for reasons similar to those that we have advanced in the case of biology. -Introduction to Heuristic algorithms in computational molecular biology, Richard M. Karp, JCSS 77 (2011) 122-128. Karps proposed: General heuristic for Implicit Hitting Set problems.

Running example: DIRECTED FEEDBACK VERTEX SET In: Digraph D Out: A minimum cardinality set of vertices that hit all directed cycles. Explicit versus implicit Hitting Set Problems Explicit: List the things that need to be hit. Implicit: The list is implicit in the digraph description (made explicit, the list might be exponential in size). Assumed

Separation oracle Find an unhit cycle if there is one P-time algorithm for approx solution of the explicit hitting set problem Algorithm for optimal solution of the explicit HS problem : things to be hit (cycles) : a hitting set (vertices) Karps generic Hitting Set heuristic: empty set Repeat:

Using the approximation algorithm, construct a hitting set for : Using the separation oracle, attempt to find a circuit that H does not hit; If a circuit is found then add that circuit to else an optimal hitting set for : Using the separation oracle, attempt to find a circuit that does not hit; If a circuit is found then add the circuit to : else return and halt

The intuition behind Karps general heuristic Quickly identify a (hopefully) small set of important cycles to cover If these are covered then probably all cycles are covered reasonable to pay for optimal solution at this point If this fails, then (win/win) a new important cycle has been discovered Quickly identify a (hopefully) small set of important cycles to cover

What to call this? Strategic kernelization in the space between implicit and explicit ? EXPLICIT DFVS I In: digraph D, and a list L of directed cycles in D Parameter: k Question: Is there a set of at most k vertices that

hits every cycle on the list L? OOPS! While IMPLICIT DFVS I is FPT, Thm: EXPLICIT DFVS I is W[1] hard. k vertex selection gadgets v k 1 of these V selected

Forward adjacency test R to B N(v) u B to R

Backward adjacency test EXPLICIT DFVS II In: digraph D, list L of directed cycles in D, r Parameter: | L | = k Question: Is there a set of at most r vertices that hits all cycles in L? Thm: This problem is FPT

Pf: (1) If r > k, then YES (2) r 2 k dynamic programming Summary so Far The design of effective heuristics is our inevitable primary mission for most problems, as theoretical computer scientists. General strategic approaches to this task throw up many novel parameterized problems, largely unexplored, as subroutines.

Plan B Two Principles We do what we have been doing: enriching the model when there is tractability deconstructing the proofs when there is intractability and there is very very much to be done, for fun and profit. Parameterized Algorithmics

Branch out! To opportunity! Focus on the unvisited core problems Find a mentor/collaborator/interpreter who is established in the area Report on NAG and examples Stefan and Fran in Australia Taking Our Own Advice II

A Report on the workshop: Not About Graphs Darwin, Australia August 58 and 9-13 Workshop Theme The focus of the workshop is to investigate opportunities for expanding parameterized complexity into important unreached areas of algorithmic mathematical science (algebra, number theory, analysis, topology, geometry, game theory, robotics, vision, crypto, etc.) beyond areas where it already has a strong

presence (graph theory, computational biology, AI, social choice, etc.). This may require new mathematical techniques. The workshop is also focused on identifying and promoting the key unsolved problems in these new directions. According to Papadimitriou, every year, several thousand scientific papers use the words NP-complete or NP-hard. Example: Computational Logistics

Trains! Regular meeting: ATMOS NP-hard classic problem TRAIN MARSHALLING In: Partition of [n] Ex. {1, 3}, {2, 4, 5} Parameter: k k=2 Question: Is k enough? YES 123|45 12 345

Example: Computational Geometry Problem! Most of the classic problems are in P. Not a problem! enrich the model In: A set of colored points in the plane. Parameter: k Question: Are k lines sufficient to dissect into monochrome regions? Good news: NP-hard! Example: Computer Vision

SEGMENTATION In: matrix of grey-scale values Parameter: k Question: Can the matrix be segmented into < k regions? 3 4 1 2 4

3 2 1 2 4

3 1 3 2 4 3

1 2 4 3 2

1 2 3 Question Should we do this again next year in Germany? MaybeGabor Erdelyi has offered to host.

Proposed acronym: DECON Open Problem How does kernelization as we know it interact with real practical computing and heurisitcs? Thank you

Recently Viewed Presentations

  • Assessment Review Board

    Assessment Review Board

    FIPPA. and s. 9 of . SPPA. 2016-10-28. Environment and Land Tribunals Ontario. Examples of Confidentiality Requests at the ERT. personal health information. financial information. new research awaiting publication. location of endangered species. 2016-10-28.
  • Literacy partner Training

    Literacy partner Training

    , get help today from your LPC or coach for both Education Connection and RRISD registration . Returning LPs . stay at least until 1st hour break. New literacy partners . stay for both hours. Complete the . exit survey...
  • Book of Esther

    Book of Esther

    (אסתר פרק ז) ARMITAGE, Edward The Festival of Esther, 1865 Royal Academy of Arts, London REMBRANDT Harmenszoon van Rijn Haman begging Esther for mercy , 1655 National Museum of Art of Romania, Bucharest "ה וַיֹּאמֶר הַמֶּלֶךְ אֲחַשְׁוֵרוֹשׁ, וַיֹּאמֶר לְאֶסְתֵּר הַמַּלְכָּה...
  • Topic: Chapter 8.1-8.2 - Japanese Culture

    Topic: Chapter 8.1-8.2 - Japanese Culture

    Ch. 8.1-8.2 - Japanese Culture EQ: How did China influence Japanese Culture? Location 120 miles off coast of Asia Made up of 4 larger islands and over 4,000 small islands Mild climate with plenty of rain Closest Neighbors are China...
  • RICAS: English Language Arts/Literacy Informational Session

    RICAS: English Language Arts/Literacy Informational Session

    It replaces the PARCC assessment and will be administered to students in grades 3 - 8. Students will take the test that corresponds to their grade level. The assessment will be delivered online using the TestNav8 platform. This is the...
  • Physics 121, April 24. Heat and the First

    Physics 121, April 24. Heat and the First

    We thus conclude that CP - R = CV or CP - CV = R. First law of thermodynamics. The internal energy. Up to now we have assumed that the internal energy U of a gas is equal to (3/2)kT....
  • Kein Folientitel - MPN Advocates

    Kein Folientitel - MPN Advocates

    MPN Horizons 2016, 11-13 November 2016, Belgrade, Serbia Nicolaus Kröger ... method of usage, & to collect safety data etc. Phase III: Objectives To assess overall and relative therapeutic value of the new drug efficacy, safety, and special properties To...
  • Forensics - DNA analysis

    Forensics - DNA analysis

    Forensics - DNA analysis RFLP History Southern analysis Fragment length analysis Frequency Pattern used to identify individuals Minisatellite Variable Repeat Polymorphism (Analysis) First locus identified: D1S8 1990, Alec Jeffrey 19 bp for each repeat containing highly variable 1 bp in...