An example where the algorithm of Hopcroft and Karp performs poorly?

I have been trying to construct an example, where Hopcroft and Karp’s algorithm for the maximum matching problem performs poorly (say at least $ \Omega(\log n)$ rounds). However, all the examples I came up with where solved on paper in almost constant number of rounds.

Other questions here in the community targeting this problem tackle the worst-case running time or the time-bound proven in the original paper.

This running time seems to be a bit too loose, especially because the maximum matching problem in general and in bipartite graphs lacks a conditional lower-bound on its running time and I couldn’t find any tight lower-bound on the number of needed rounds. I couldn’t find a bound on the number of needed operations in constrained models of computing either (For example binary decision tree or so).

On the other side, the $ O(\sqrt n)$ bound on the number of rounds from the original paper has not been improved since was found in the 1973 except in the parameterized context and in special classes of graphs.

Any ideas/suggestions are much appreciated 🙂

Google Script – Extract Value from Poorly formed JSON result

I have a Google script that returns the following result set, but when I try to get the value for asking_price or asking_price_condition it comes back undefined. I assume it’s because of some {} subsets are nested in the result. any help.

{manheim_sequence=30, option_air_conditioning=true, option_rear_park_aid=false, gross_vehicle_weight=6950, year=2017, option_tilt_tele_wheel=true, intake_date_old=null, seats=Cloth, manheim_maa=5208221, option_non_factory_exhaust=false, option_power_windows=true, manheim_submitted_on=2018-11-28T15:04:57.000-05:00, transmission=Automatic, ext_paint=White, option_cd=true, option_power_door_locks=true, product_id=88423, needs_transport=false, vin=1C6RR7LM7HS874776, model=1500, id=88495, fuel_type=Diesel, option_airbags=true, arrival_date=2018-11-15, mileage=8098, option_adj_pedals=false, option_air_susp=false, option_chrome_wheels=true, option_pan_roof=false, option_wireless_cell=false, option_alum_wheels=false, option_dvd=false, drivetrain=4 Wheel Drive, option_dual_climate_control=true, engine_cylinders=6 Cylinder, option_alloy_wheels=false, option_altered_suspension=false, condition=4.3, active_admin_comments=[Ljava.lang.Object;@35547aa4, option_cruise_control=true, option_power_steering=true, manheim_auction_number=14, option_running_bd=true, style=Big Horn 4x4 Crew Cab 5'7" Box, option_premium_sound=false, option_moonroof=false, custom_description=Bought from AB , option_power_mirrors=true, option_rear_window_defroster=false, option_addl_rear_seat=false, trim_level=Big Horn, has_unibody_damage=false, option_power_seats=true, option_tinted_glass=false, has_title=null, option_child_seat_anchors=false, clean_code=TD, owner_partner={website=, bill_address_id=5168, manheim_auction_price=100, role=0, is_active=true, ship_address_id=5169, qb_edit_sequence=1550083245, sales_contact=BRIAN PIGER 717-553-3080, created_at=2016-05-19T14:41:00.000-04:00, qb_list_id=80000983-1463508945, manheim_maa=5208221, client_id=4, alt_phone=, account_id=KELL3, resale_number=5208221, updated_at=2019-02-13T13:43:46.000-05:00, phone=7175533080, partner_category=1, name=KELLER BROS DODGE, manheim_auction_highline_price=150, id=4609, fax=7176261885, email=bpiger@kellerbrosdodge.com}, option_power_brakes=true, option_rear_ac=false, option_heated_seats=null, oem_int_color=Diesel Gray/Black, option_heated_p_seat=true, make=Ram, manheim_lane_number=9, option_antilock_brakes=false, option_sat_radio=true, product={custom_option_assignments=[Ljava.lang.Object;@3a5e5ef2, notes=, system_stock_number=10050730, expense_total=10, buyer_id=51, product_category_id=4, sale_note=, external_url=, product_status_updated_by=Jimmy Harish, id=88423, estimated_value=30300, payment_received=false, total_spent=10, product_status_id=2, location_vendor_id=null, owner_partner_id=4609, sold_to_partner_id=null, as_product_type=Car, payment_reference=, created_by=Charlie Null, stock_number=10050730MS, report_value_adjustment=0, location_notes=, product_status_updated_at=2019-02-18T15:34:03.000-05:00, retail_user_id=null, purchase_price=0, updated_by=Bill Spencer, purchase_date=2019-02-18, payment_deposit_date=null, asking_price_condition=, transport_partner_id=null, created_at=2018-11-15T08:44:29.000-05:00, buyback=false, intake_date=null, gl_payment_line_id=null, product_images=[Ljava.lang.Object;@445d7c3a, purchase_fee=0, primary_image_id=null, updated_at=2019-02-21T12:29:50.000-05:00, sale_date=null, price_bid=0, location_customer_id=null, sale_reference=, gl_payment_line_payment_index=null, sale_fee=0, vendor_partner_id=null, in_arbitration=false, payment_status=0, serial_number=1C6RR7LM7HS874776, location_vendor_name=, sale_price=0, location_type=1, location_customer_name=, current_product_purchase_id=55783, asking_price=32800, record_complete=true}, general_description=BRIGHT WHITE CLEARCOAT, A/T, CLOTH, DIESEL, 4WD, V6, AIRBAG S/C, A/C, DUAL CLIMATE, PWRDL, PMIRRORS, PSEATS, PWRW, CHROME WHEELS, HTD D SEAT, HTD P SEAT, CD, SAT RADIO, RUNNING BD, 6950GVW, BOUGHT FROM AB , option_heated_d_seat=true, option_backup_cam=false, option_air_bag_side_curtain=true, option_active_susp=false, title_date=null, option_non_factory_wheels=false, option_dual_moonroof=false, option_child_seat=false, option_sun_moon_roof=false, oem_ext_color=Bright White Clearcoat, int_color=Gray, option_navigation=false, option_conv_ht=false, option_altered_intake=false}