¿Cómo usar una clave principal incrementada automáticamente como clave externa también?

Parece que tiene las tablas de referencia y referenciadas al revés. Es posible que desee hacer:

ALTER TABLE `child ` ADD FOREIGN KEY (`parent_id`) REFERENCES `parent` (`id`);

También puede definir la clave externa en CREATE TABLE declaración, de la siguiente manera:

CREATE TABLE `parent` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `data` text,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=3 DEFAULT CHARSET=utf8;

CREATE TABLE `child` (
  `parent_id` int(11) DEFAULT NULL,
  `related_ids` int(11) DEFAULT NULL,
  KEY `parent_id` (`parent_id`),
  KEY `related_ids` (`related_ids`),
  FOREIGN KEY (`parent_id`) REFERENCES `parent`(`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Caso de prueba:

INSERT INTO parent (`data`) VALUES ('test data 1');
Query OK, 1 row affected (0.01 sec)

INSERT INTO parent (`data`) VALUES ('test data 2');
Query OK, 1 row affected (0.01 sec)

INSERT INTO child (`parent_id`, `related_ids`) VALUES (1, 100);
Query OK, 1 row affected (0.01 sec)

INSERT INTO child (`parent_id`, `related_ids`) VALUES (2, 100);
Query OK, 1 row affected (0.01 sec)

INSERT INTO child (`parent_id`, `related_ids`) VALUES (3, 100);
ERROR 1452 (23000): Cannot add or update a child row: 
  a foreign key constraint fails